The upcoming dungeon does not have any gimmicks like the MagiTek Factory's vulnerability to Magic. You'll want to form a full party capable of dealing with many kinds of threats, and you'll want a large variety of Spells at the ready. Terra has to be present for plot reasons.
Imperial Base
You would expect the Imperial Base to be crawling with guards, but when you arrive you find that it has in fact been abandoned. The locked Treasure room remains locked, so the only place to go is up the stairs and east towards the exit. You'll appear on the World Map, with the entrance to the Cave to the Sealed Gate just across a bridge to the east.
Cave to the Sealed Gate Encounters
There are five types of Monsters you will find in Cave to the Sealed Gate Encounters. The general rule is that you'll earn a lot of Exp but not as many Magic Points as you might like. The most common Monsters on the upper floors are Apparites. Their basic attacks represent little threat, and the worst they can do offensively is inflict Seizure. However, they have a 1 in 3 chance of countering any attack that doesn't finish them off with Imp Song, an annoying ability that turns the party into Imps. If you happen to have Status protection, have at them, but otherwise you'll want to exploit their weaknesses to Ice and Pearl with Spells or Abilities (e.g., AuraBolt) to take them out in one shot.
The other common upper floor enemy is the Lich, an undead for with nonstandard weaknesses. Rather than having a vulnerability to Fire, they are healed by it. Pearl works but you have limited means to exploit that weakness. Fortunately they have only 590 HP and are highly vulnerable to physical attacks. Take them out quickly when they are using Fire and Mad Touch (which causes Muddled), as they will ramp up to using Fire 2 and even Fire 3, given enough time. When only a single Lich remains on the battlefield, it will tend to cast Fire 3 to the exclusion of all other attacks.
The Monster you'll likely see least frequently is the Coelecite, a Fire-imbued scorpion. Like Apparites, they are vulnerable to Ice, and they absorb Fire like Liches. They can use HypnoSting to inflict Psyche but are otherwise the least threat when encountered in mixed groups. They try to use Magnitude8 when they die as the last Monster on the battlefield, but lack the MP to make that happen. Therefore, it is safe to leave them for last.
Starting in Basement 1 and continuing to the end of the Cave, you'll encounter Ings. These things are tough with 1,100 HP and tend to use the powerful Lifeshaver attack. As an HP-draining attack, it cannot do more damage than the amount of HP the Ing has lost, but it's powerful enough to do well over 500 damage at a shot. It's the only Earth-Elemental Ability in the game that is not blocked by the Float Status.Your best bet is to kill them quickly so they don't get a chance to use it. Ings can only use Lifeshaver every other turn, so your best bet is to coordinate an attack right after they use it (hopefully for 0 damage). They are weak to Water and Pearl, but any powerful attacks should work when made consecutively.
Finally, there are Zombones, the most common Monsters on the lower levels. They have the most HP by far of the basic Monsters in the Cave to the Sealed Gate and a powerful basic attack, but no special counterattacks or anything else to worry about. They will eventually use Bone to inflict Zombie, but not until the fourth turn at the earliest. Take advantage of their relative vulnerability to Magic in general, and Fire and Pearl specifically, to cut through their 1,991 HP before they do.
The Upper Floors
You'll find a chest in plain sight in the Entrance cavern. This contains the Assassin, an interesting Weapon for Locke that you should definitely not use. There is a theme in this dungeon of powerful Treasures that are nonetheless very bad within this dungeon. The Assassin randomly Wounds Monsters, which would normally be great. Against undead, though, it always restores them to full HP. The only enemy found here normally that isn't undead is the Coelecite, and the Assassin isn't needed for them. Keep it in mind for later, though. Shadow can use it as well.
The left staircase in Basement 1 leads to the Tempest. This is an interesting Weapon for Cyan, as half the time it will use Wind Slash rather than making a normal attack. This isn't generally bad in this dungeon, but Wind Slash hits all enemies and thus will give groups of Ings some damage to recover with Lifeshaver. It's best to play it safe in such encounters.
Basement 2 is the first puzzle area of the cave. A series of bridges will flip back and forth between two layouts. Note which squares are always present, and make sure you are always standing on those when the switch happens. There are two chests here. The one in the bottom left contains the Coin Toss, a Relic that changes Setzer's Slot Command to GP Rain. This is costly and not terribly effective at this level. The upper right chest contains an X-Potion. Once you've collected the Treasures, you'll want to head to the lower right platform to continue on.
Basement 3
You'll find yourself in a giant room consisting of stone islands floating in a sea of lava. You're immediately faced with two paths. The eastern path loops around south and leads to an Ether, while the southern path continues through a tunnel to the east. There is a short bridge to nowhere to the northeast, but ignore that for now and continue southeast instead. You'll climb a slope then come to a bridge with a switch on it that looks distinctly like some kind of trap. Despite that, push the switch—you'll fall down to the platform below, but a bridge to a Genji Glove to the northwest will also appear. Grab that and head east once more.
You'll see a plateau with two switches. The left switch opens a door to a Small Room with a Tent and a save point. You'll definitely want to hit this switch first, because the other one summons a dangerous Ninja. This is an entirely optional encounter with meager rewards. The Ninja is extremely dangerous, throwing various skeans for high damage and responding to Fight by giving himself Clear Status. Respond to that with Magic, but avoid Poison. The Ninja is weak against Thunder and Pearl. Once defeated, the Ninja will give a hint about some upcoming Treasures.
Resuming your trek east, you'll see another switch on a bridge. Given what happened last time, and the fact that this bridge is over lava, you may be hesitant to press the switch. You must, though, as doing so creates a staircase south to the next area. This is the area the Ninja was talking about, and aside from the visible chest containing an Ether, there are three other treasures to be found here. Starting from the bottom tile of the bridge, take one step down and one step left and search to find an Inviz Edge. Note that unlike other hidden treasures, these are triggered by where you're standing, not where you're facing. From the Inviz Edge, take six steps south and search to find a Soft (which the game incorrectly indicates is a Remedy). Four steps up and four steps right from there you will find a Water Edge. You can find 293 GP claiming to be 2,000 GP four squares above the chest.
Enter the passage to the east and work your way north to the exit near a chest containing an Elixir. East of here you'll find a number of switches. You can avoid the eastern switch and access the chest, but if you step on that switch you'll need to take an alternate method. For now, head south and west to another switch. This opens a door to a treasure room where you'll find two Magicites, an Ether, and the Atma Weapon. This is possibly the best Weapon in the game…just not right now. It ignores Defense and its damage scales up based on your level but down based on how much of your HP you've lost. At your likely current level, it's not very effective, but that will change in time.
With the Atma Weapon and other Treasures recovered, head east to the second set of vertically-aligned bridges. The switch at the end of the first bridge will align the platforms so you can cross east, and the switch on that platform lets you return west on the next level up. You don't actually have to do this, but it lets you access that chest you may have missed. It contains a switch, as it turns out, and one without a clear purpose. Instead, head north and grab the Magicite hanging off the bridge, then continue southeast to the next area.
The Gate Cavern leads to the Sealed Gate, where Terra will call to the Espers. Kefka will appear and attack, though it is not a true boss battle and it will end as soon as you do anything to him. This triggers a dramatic cutscene, after which your goal should be to return to the Blackjack. A new doorway at the south end of the room leads directly to the Entrance, making for a short trip.
You'll pass through the still-abandoned Imperial Base on your way back. When you reach the west entrance, party members from the Blackjack will meet you and report on what's happened. You'll automatically board the Blackjack, which is disabled during the ensuing cutscene. You'll touch down southeast of Maranda. You can either walk or rent a chocobo in the nearby Chocobo Stable, but either way your destination is Vector.