Hilda Captured
Upon returning to Altair, you'll learn that not only was Cid's [Airship] taken by the [Dreadnought], but that Hilda was aboard at the time. Your mission is now to find the Dreadnought, destroy it, and save your allies. But where is it? Speak to various rebels including Minwu, who will indicate the Dreadnought can be found north of Fynn.
More specifically, you want to head northwest from Fynn, towards Palamecia. You could also return to Kashuan Keep and take a chocobo, but you won't want to avoid the battles on the way to the Dreadnought. Not only will they allow your party to gain strength, you can earn valuable Berserk, Scourge, and Stun Tomes from the Magicians along the way. The Dreadnought will be your toughest challenge yet, so you'll want to be in tip-top shape before boarding. Though they are obscenely expensive, it may be worth investing in a Cottage or two so you don't have to make the long trek back to town to recover MP.
Dreadnought 1F
The Dreadnought has three floors divided into a total of five maps. You start on the top floor, which is crawling with imperial Captains. One is blocking the entrance ramp, but you can show him the Pass to get by. If you don't have a Pass, you'll have to defeat him instead. Speaking to any of the other wandering guards will trigger fights as well. These fights are not unwinnable, but Captains have a ton of HP and Defense and make six powerful attacks per round. They are best avoided. (They do have a number of fantastic drops, but you can also fight them in Fynn if you want a safer way to farm them.)
The most common Monster on the floor is the Ghast, which can appear alongside Ghouls, Shadows, Wererats, or Wraiths. You've seen all of these before, and should be able to handle them here. You'll also find Mines here. Their Self-Destruct can be mitigated with heavy Armor, but your mages will be very vulnerable so take them out quickly like their brethren.
More rarely, you will run into Werepanthers, sometimes accompanied by Soldiers and Magicians. The Werepanthers are tough and have a powerful, Poisonous attack. They are Werebeasts, though, so the Werebuster will do a number on them. This is also true of another uncommon Monster here, the Stunner. These are beefier versions of Wererats whose attacks inflict Paralysis rather than Poison. This won't prevent your Characters from gaining attributes after a fight, but they can easily lock down your front row.
The Dreadnought is not laid out like a typical dungeon, and you have several paths open to you. The stairs leading to B1A can be found in the middle of the room. You'll see a treasure chest in a locked jail cell with no obvious entrance. You can walk through the door on the western side of the cell to open it and unlock a Sleep Blade. It is guarded by a combination of Sergeants, Magicians, and Soldiers. The rest of the floor can be reached via other stairs, so this is a good place to start your Treasure hunting. The Sleep Blade is similar to the Ancient Sword in that it is powerful and inflicts a Status Ailment (predictably, Sleep), but lacks Accuracy. This makes it a fairly questionable weapon for basic use, and you may want to train up any sword-wielders to use spears or axes for the next few parts of the game.
The stairs to the north lead to a walkway that holds three doors, all of which lead to trap rooms. At the western end of the walkway is a chest containing 400 gil. The eastern end of the walkway instead turns south and leads to the other two staircases on 1F. The first, reachable via an eastern branch, brings you to the rest of B1A, including the cell holding Hilda and Cid. Follow the original path considerably further and you'll find yourself on B1B, on the path to the Dreadnought's engines.
There are a number of ways to proceed, and you'll want to plan ahead. You cannot Teleport or Warp out of the Dreadnought, but you are free to leave to go back to town or use a Cottage by simply walking out. Once you rescue Hilda and Cid, that is no longer the case—an imperial guard will block the entrance and you'll have to destroy the Dreadnought to leave. For that reason, you may want to gather up all the available Treasures before rescuing anyone, then leave to heal up and save. This walkthrough will follow the shortest route (starting with B1A), but you can enter either branch to start.
The other section of B1A is a path that splits off into four rooms. You'll find the Dark Bow in the westernmost room, the Thief's Gloves and the prisoners in the central rooms, and two Potions in the eastern room. Remember that once you free the princess, you can't leave the Dreadnought until it is destroyed.
Dreadnought B1A and B1B
The larger section of B1A starts as a hallway that splits several times as it moves south. At the intersection, the eastern path leads to a small room containing two Potions. You'll also be able to see the prisoners from here, though not reach them. The western path from the main hallway quickly splits a second time. Keep along the west wall to find the Dark Bow. This is another low accuracy Weapon like the Ancient Sword and Sleep Blade, though it may see some use if you have a mage with a bow used as a reserve Weapon. Its Darkness effect can blunt the physical attack of many enemies if it hits.
The central path (west and then east from the stairs to 1F) splits again, leading to two rooms. To the west you'll find the Thief's Gloves, an absolute beast of a piece of Armor. They offer more than double the Defense of the Mythril Gloves as well as +15% Evasion—+5% from a lower penalty, and another +10% from a +10 bonus to Agility. Whether used to make a high-Evasion fighter almost unhittable, or shore up the Evasion (and thus Agility growth) of a slower fighter, the Thief's Gloves are amazing and will serve you well throughout the game. Don't miss them! (Amazingly, they can be purchased for the low price of 1,000 gil, but not until you reach Mysidia.)
The room east of the Thief's Gloves holds Cid and Hilda. Interact with the bars twice to open the cell, and speak to Cid to free the pair. Be aware that once you do this, there's no way to leave the Dreadnought short of destroying it. If you want to collect more Treasures before triggering that limitation, leave the pair in their cell for the time being. This will add a significant amount to the time you'll spend in the Dreadnought, but if the alternative is a party wipe, this is a small price to pay.
Once you've rescued Cid and Hilda, or if you want to collect the last few Treasures in the area first, you should head to B1B. To get there, return to the long pathway that led from the walkway on 1F and follow it to its end. B1B is a very simple floor, consisting of a U-shaped hallway with no obstacles or Treasures on it. There is one new Monster here, though you will encounter them only rarely: the Helldiver. These birds are essentially less dangerous Werepanthers. They have no Elemental weaknesses and will take a few hits to defeat due to their 140 HP and 17 Defense. They have a powerful two-hit attack, so prepare for that or try to take them out before they can deal too much damage.
Dreadnought B2A and B2B
B2A is another largely simple floor, though it contains a few points of interest. First, it is crawling with Captains which will pull you into combat if you speak to them, so avoid that. Second, you'll find a group of four chests in the northeast corner, past the stairs in the center of the room. The stairs lead onward, but the chests contain some amazing gear you won't want to miss. These are the last Treasures along this route, so once you collect them, feel free to leave the area and save if you haven't yet saved Hilda and Cid.
The left chest contains a Trident, a significant upgrade over the Mythril Spear for any spear users in the party. The second chest contains the Main Gauche, a unique and extremely useful knife. In addition to its impressive stats, it offers a high Evasion bonus (+5%) rarely seen on a Weapon. This allows even a mage to rack up a respectable Evasion by leveling up their knife skill. This can be very useful for getting Agility increases without incurring a significant magic penalty. The third chest is guarded (more on that in a moment), and the eastern chest contains a Giant's Helm. Like the Thief's Gloves, it grants a bonus to an attribute, though in this case it grants +10 Strength rather than Agility. It does incur a significantly higher Evasion penalty than the Mythril Helm despite only a moderate increase in Defense, but the extra damage you can deal is worth the tradeoff.
Finally, the second chest from the right contains an Ice Shield, but is guarded by a Hill Gigas and possibly a Magician and/or Soldier. The Hill Gigas has an extraordinary 750 HP, along with the same 60 Defense as an Adamantoise. It gets three attacks, each hitting for 100–200 damage, which will likely be fatal for any front-line fighter without a lot of Evasion. If you can get a mid-level Blink up on someone with high Evasion, you can largely blunt the Hill Gigas's attack, allowing you to whittle away at its HP. It has no Elemental weaknesses or resistances, so Spells are your best bet but won't take it down quickly. The effects of the Ancient Sword, Sleep Blade and Dark Bow can all prove useful as well. This is the closest thing the Dreadnought has to a boss, so tread carefully. The Ice Shield is not a unique item, so you may want to skip this chest entirely.
Once you're ready to head for the Dreadnought's engine (i.e., you've rescued Hilda and Cid), return to the center of B2A and climb the stairs. They lead to a small area in the middle of B1B that continues with another set of stairs to B2B.
B2B introduces a rare Encounter with Sergeants, Magicians, and Soldiers, but it's nothing you can't handle—especially if you defeated the Hill Gigas. What makes this floor interesting is its layout. It is a grid of halls, and your destination is a door in the middle of the area. You start off in the northwestern part of the floor, but many intersections are guarded by Captains. Even fighting and defeating them will not remove them from the map, so you'll have to maneuver around them, working your way around the perimeter of the map until you can reach the door.
To find the door without incident, head north, then west, then south along the western wall. Take either of the eastern halls when you reach them, then head south to the southern wall and proceed further east. Take the fourth path north (the last path before the guard in the southeast corner), then go east to the eastern wall and follow it north to the end. Head west past the first hall, which contains a guard, turning south at the next. From there, head west, south, then east, and you'll find the door to the engine room.
There is no boss in the Dreadnought, nor any need to fight your way out. Simply use the Sunfire on the engine in the center of the room, and you'll find yourself on Cid's [Airship], headed back to Altair. Note that if you have not yet rescued Hilda and Cid, you will not be able to use the Sunfire.