Bahamut (Ultimate Summon) Location and Guide
When you get your Airship back on World 3 you'll be able to complete the sidequests for both the Phoenix Summon as well as the Bahamut Summon. You won't be able to access either of these locations with your Airship though, instead you'll need to fly your Airship over to Mirage Village (Phantom Village) and get the Purple Chocobo from there then fly the chocobo to the desert where you can find Phoenix Tower and North Mountain.
If you're wandering around lost in Mirage Village looking for the Purple Chocobo, I recommend you read my Piano Master Guide since that goes into much more detail about how to reach the Purple Chocobo in this town. Once you've obtained the Purple Chocobo you'll want to fly to the northeastern most portion of the world where the big desert is. Use my map below for some extra guidance.
When you arrive at the forest with the Black Chocobo you'll want to travel to the north and keep an eye out for the large oval mountain range surrounded on three sides by deserts. If you travel to the southern portion of the desert, that's where you'll find the tower which houses the Phoenix Summon. After Bahamut, head over there next. When you enter North Mountain you'll probably remember the area from earlier in the game.
The whole area is rather straight forward, you run through the dungeon (which is filled with lower level enemies) until you reach the peak. When you do reach the peak Bahamut will speak to your group before challenging you to a fight. When you best him in battle you get the Bahamut Summon.