After exploring the world in Setzer's Airship, you should go to the Cave to the Sealed Gate in the east part of the Empire's contintent.

Prepare

Before going to the Cave to the Sealed Gate, buy as many Fenix Downs/Phoenix Downs as you can afford. Put Terra in your party, then go to the Imperial Base east of Vector and Albrook.

Imperial Base

After the brief cutscene in the Imperial Base, go north to find stairs. Go up them, then go east and down the stairs. From there, go east to enter the Cave to the Sealed Gate. (Note that the house in the Imperial Base has treasures in the basement, but they are behind a locked door.)

Cave to the Sealed Gate

When you encounter Ings/Outcasts and Zombones/Zombie Dragons, use Fenix Downs/Phoenix Downs or Life/Raise spells on them to kill them instantly.

Follow the path, and open the chest that you see on the right. Then go south. When the path splits, go down the west path to find a chest, then go back and take the east path down.

To get past the changing bridges, go east along the bridge, pushing to the right until the bridge changes, allowing you to reach the northeast corner and open the chest. Then go west onto the same bridge that you were on a moment ago, and stand on the second tile from the right until the bridge changes. When it does, go south, and when you can, go west toward the chest on the left. After opening that chest, push toward the right until you are back on the little island in the middle. From there, when the bridge south of you looks like an upside-down F, walk onto the farthest point of it. Then when the bridges change, go south to the southwest island. Then push eastward along the bridge that leads to the southeast island. When you have gone across, go through the southeast exit to go to the next area.

Go east and follow the path to find a chest. Then go north to where you entered, and from there, take the south path.

After going under the stone bridge, go south, then up the stairs, then go east and flip the switch. Go west and follow the path to find a chest. Then go back to where you fell, and go east.

You will find two switches. Flip the left one. (Flipping the one on the right will make a Ninja attack. You will have future opportunities to fight Ninjas, but you can fight one now if you prefer.) After flipping the left switch, a door will open. Inside, you will find a save point and a chest.

Exit the save point room, then go east and flip the switch on the bridge, then go down the stairs that appeared. At the bottom of the stairs is an area with hidden treasures. Examine the ground at each of these spots.
1. Left of the stairs.
2. Above the door on the right.
3. To the left of the ramp up to where the chest is.
4. In the center of the outcropping above the chest.

After finding the hidden treasures and opening the chest in this area, go east into the cave opening. You can't go through to the east side, but there is a hidden passage that goes north. Keep going north, and if you can't go farther, try going west or east, then try going north again. When you get out of the hidden passage, you will be north of a chest. Open it, then go east and step on both switches in the ground. Afterward, go south, then go west until you see another switch in the ground. Step on it, then go into the room that opened. Open all the chests. The "Magicites" in here are not Espers, but just shards of Magicite that you can only use once, summoning a random Esper.

Exit the room where you got the Magicites, then go east to the second bridge. Go north, flipping all of the switches along the way. If the bridge to the east is broken, go west and flip the switch inside of the chest.

Go east and open the chest to the north, then go southeast to reach the exit. If nothing happens when you try to go through that exit, walk around until you have an enemy encounter, then try again.

In the next area, just go north and enter the large cave. A cutscene will take place. Hit Kefka once with a regular attack.

After the cutscene, go south from the Sealed Gate, and use the south door, which goes to the first room of the cave. Exit the cave and go through the Imperial Base. There will be a cutscene when you approach the exit of the Imperial Base. Later, you will crash on the Empire's continent, near Maranda. You won't be able to fly the Airship afterward, but you can still change party members and heal up inside. Leave the Airship via the exit near the merchant and the guy who heals everybody, then go northeast to Vector.