I really don't think it matters. He could have use Fossil Roo to go back, he could have built a bridge made of rocks, he could have caught a ride on a Zuu -- it's just a plot device. It's used throughout the game, and the swimming assertion isn't too far-fetched -- Quina does it to get back to the Mist Continent from Madain Sari...s/he also shows up in Lindblum after the Alexandrian Alexander tragedy somehow, too...EDIT: I think the better question is how Zidane and Tantalus and everone got back to Alexandria so fast from Lindblum.
I like to think he took the elevator leaf from inside the tree and surfed back, which is as good a guess as anyone else, I s'pose. =p