You have to go to the Citadel, go through it and get the Rat Tail, then give it to Bahamut. The Citadel is in the north-central part of the map. You can either fly your new Airship to the tip of the peninsula and walk a ways, or you can sail to the mouth of the nearby river and switch over to the canoe, which involves less walking. Once you get through that, you have to take your prize to Bahamut, who can be found in the caves in the archipelago just southwest of the Citadel. There are no random encounters in these caves, and a crapload of loot, so feel free to walk around inside.

Don't forget, once you get changed into your better characters, fly around for a while and see what else you can get. Ninjas and Knights can now use magic (black and white, respectively), and your Wizards can now equip better items and learn better spells.

And the Fairy costs, I think, 50 grand. I don't remember where on the map it is, but it's hidden. It's in a desert, and there's a little patch of desert that's seperated from the rest of it, and that little patch is just west of a little patch of forest. So land your airship and walk across the small desert and into the little patch, and the caravan should be there.