Where we last left our party in Zozo, head back around south to reach Jidoor. Go to the house in the North of town and talk to the Impressario, he'll drop a note and tell you Celes looks like Maria. Pick up the note and head south out of town to the Opera House. This will be the last you'll spend in this area for a while so make sure you're satisfied with your party and don't need anything else here. Talk to the Impressario to get Celes to take Maria's place and prepare for the opera house sequence. Make sure someone other than Celes is wearing Sprint Shoes, because one of the next sequences will be timed.
First, have Locke head towards the dressing room to the south east of the seats. Go to the right room and talk to Celes, and have Celes review the script. Then head onto the stage, your first line is "Oh my hero." Your second line you have to select is "I'm the darkness." Your last line is just "Must I." Your next task is to talk to the prince three times and follow him as he dances, then pick up the flowers and throw them from the top of the balcony. Do this in time and you'll complete Celes' part of the scene.
Take over as Locke, and you'll find a letter. Talk to the Impressario back in the seats and you'll be on a five minute countdown to stop Ultros. Head to the top right and flip the far right switch to open a door, then go through the top left door to find yourself on the balcony above the stage. Avoid the rats if possible and just make your way over to Ultros, keep in mind the clock ticks even on the inventory screens. Always kill the Vermin first since they can summon replacements. After you reach Ultros, he'll drop the weight and you'll have to fight him. Use the chainsaw if you have Edgar and your most powerful attacks, including any lightning magic. He'll fall eventually.
In the next scene you'll flip a coin to see whether or not Setzer will assist your party. If Edgar is in the party, Celes will pick up the coin from him. The coin is revealed to be double-headed. If Sabin is also in the party, Sabin will recall that this is the same coin they flipped to decide who received the kingship.
Once you land, you'll be able to buy items and heal in the airship at any time, as well as unequip those members not in your party. The town near you is Albrook, explore it and buy equipment as necessary. At the southwest of the continent is Maranda, which is also where all the letters from the soldier on the Veldt are being sent. You can check on the status of his girl and get some more equipment and armor. At the north of the continent is Tzen, which offers some interesting relics, including the black belt relic which lets you counter-attack when hit. Chocobo stables can be found in the forests near most of these towns, and in general. When you're ready, head for the center of the continent to find Vector. I wouldn't recommend sleeping in the inn since your host may steal your money. Loot the place for items and talk to people, then talk to an old man at the east of town to sneak in. Jump on the crate and sneak your way inside. Enter the bottom right tube and the tube at the top of the path for some treasure, then take the other bottom tube to move on.
In the next area, travel to the right and through a tube in the wall for a room with more treasure chests. Travel up the stairs to the left for a treasure chest in the previous room, and you can take a path and some stairs to reach some more treasure chests accessible through doors in the bottom wall. At the top of the area you can step on a conveyor belt dropping off armor to go to another scene and watch Kefka throw away some Espers. Follow them. Go to the door on the left to save and talk to the leftmost Esper to fight it. Attack Ifrit with ice or your most powerful attacks and hit Shiva with fire. Eventually they'll recognize Ramuh's power, talk to both of them in turn and you'll gain two more Espers. Go through the right door and climb the stairs. Search the bottom left corner of the room with the tubes to find a break blade. You'll fight the number 024 boss.
Empty Celes of her equipment, and flip the switch at the top of the room to get 6 pieces of magicite. Celes will leave your party, and Cid will offer you a ride out. Follow him and save your game. Equip some of the new espers on your party since they will likely teach you spells faster than your old ones. Talk to Cid to take a ride out on the train, at the end of which you'll fight a boss.
The boss is Number 128 (common steal: None; rare steal: Tempest). Make good use of your Espers and Edgar's Auto Crossbow to take this boss down. Be careful, though. This can be a tough fight if you come unprepared. Try destroying the left and right blades before the body to avoid taking too much damage. With practice and persistence, you'll beat him.
Head out of the city and Setzer will join your party and you'll fight another boss together. You'll wind up back in Zozo with Terra, and begin a special scene where you control Maduin in the Esper World. Talk to as many people as you'd like, and eventually choose to return with the girl at the north of town. Talk to the girl in her bed to advance the plot. Next, go to the gate at the north of town to talk to the girl again, Maduin and her will have a child named Terra. In the next scene, talk to the elder and go to the gate again to complete the scenario.
You'll end up with control of the airship and Setzer in your party.