It's easy.

(SPOILER)First, you need to have defeated Lich (since you're in the Earthgift Shrine I'm going to assume to did that already).

Second, sail over to Crescent Lake Village.

Third, once you're in the village talk to the circle of sages. One of them will give you a canoe.

Fourth, get back in the ship and sail along the coast of the continent that's slightly north of where you docked to get to crescent lake. You'll eventually come to another dock.

Fifth, walk around until you find a lake. Canoe around in there and eventually you'll find the Ice Cavern.

Sixth, explore every last inch of the ice cavern (which has very tough enemies) until you find the Levistone.

Seventh, take the Levistone to the Dessert south of Crescent Lake village. Doing this will obtain you the Airship.

Eighth, fly to the "Eagle shaped" continent in the north-east. On the westernmost extremity of this continent is a castle. Land the airship as close to that as you can get.

Ninth, walk to the castle. It is called the Citadel of Trials.

Tenth, explore the castle until you find the Rat's Tail.

Eleventh, go back to the airship and fly to the archiapelago between the two northern continents. In one of the holes in the ground you'll find Bahamut, who'll upgrade your party.