Leave Kaipo and head northeast, through the desert, until you see a cave: the Underground Waterway.
Underground Waterway South
From the cave entrance, go north across a bridge and up a set of stairs for two chests with Potion and Maiden's Kiss. Return to the entrance, then head west, across a bridge. Take a detour to the south for another chest, with a Tent. Cross the bridge to the north to meet Tellah. He explains that he is on his way to Damcyan. However, he's not strong enough to defeat the monster blocking the way. He joins your party, figuring that if you combine your power, you can defeat it.
After Tellah joins your party, check out his equipment and have him equip anything you're not currently using that's better than what he has, which isn't much. You can choose to head back to Kaipo and pick him up a Leather Cap and Iron Armlet, but since you're going to get upgraded gear for Rydia soon, you may wish to just give him her old equipment afterwards instead. Stick the old man in the back row along with Rydia, and then cross the bridge to the west. If you're playing the Original version, the chest just across the bridge contains 120 Gil. Continue across two bridges to the east, then go down the stairs to the south, and back up through the waterfall for a chest with Iron Armlet.
Head back down the waterfall and walk around to the west. There is a hidden entrance in the middle tile of the waterfall. Inside the Waterfall Grotto are three chests with Phoenix Down, X-Potion, and Dry Ether.
Exit the grotto, walk all the way back to the stairs on the eastern side of the room, and back to the west across the three bridges. Take the first set of stairs up and into the next area.
Underground Waterway B2
Follow the ridge to the north, across a bridge, then head down the stairs. At the first branching path in the water, go east and up two short flights of stairs for a chest with Potion. Go back down the stairs and continue south through the water. Take the longer set of stairs up, and continue west on the ridge. At the end of the ridge is a chest with Ether. Go back east, and cross the bridge to the south. After you cross the bridge, go west, and across another bridge. Enter the door in the wall.
When you enter this room, Tellah explains that this spot is a magic field that repels monsters, allowing you to rest in a Tent or Cottage, and save the game. He talks some about his daughter, Anna, who eloped with a Bard to Damcyan. Tellah talks about the monster blocking the way to Damcyan - a creature with eight tentacles - before it's too late. Too late for what? Tellah doesn't know; he only hopes his instincts are wrong.
Exit the room to the north to come back out into the main room. Cross a bridge to the west and take a short detour north for a chest with Ice Rod. Go down both flights of stairs to the south, then walk east through the water. Head up the flight of stairs to the north and through the door.
Underground Waterway B3
Head south, then cross the bridge to the west. Go south until you come to a branching path. To the east you'll find two chests with 580 Gil and Bomb Fragment. Return to the branching path and continue west, then north up the stairs.
From the entrance of this room, go west into a secret passage. The passage goes north, east, north, east, south, and east to a chest just on the other side of the wall from where you entered, holding a Feathered Cap. Head back to the main room through the secret passage, and continue north up the stairs from the entrance. Grab the Potion from the chest on the way, then continue to the next floor.
Underground Waterway North
Follow the path north, then take the staircase to the west down. Follow the path around to the west for a chest with Ether. Take the short staircase to the north and grab the Antarctic Wind from the chest. Head back to the east and cross the bridge. You'll see the stairs to the next area, but don't go through them just yet. Instead, head south, down three flights of stairs, and grab the two chests with Bronze Hourglass and Shadow Blade. Be sure to equip the new sword to Cecil.
Now, head back up the stairs and head to the next area. Tellah tells you that the stairs lead outside, and that the monster is in the cave beyond, reminding you that you can use a Tent on the overworld to heal up. And, don't forget to save, too!
There is a large waterfall as soon as you enter. When you approach, you fall down the waterfall to the next level. Take the stairs and follow the path around to the south. When you come to a large staircase, go down it for two chests: Hades Helm and Hades Gloves'. Again, equip these to Cecil right away. Go back up the stairs and cross the bridge, then go through the door.
Underground Lake B1
Head east across the bridge and open the two chests for the last piece of armor for Cecil: Hades Armor. The other chest contains Hermes Sandals, which is not equipment, despite the name. Cross the bridge to the north, take the stairs down into the water, and heal up before approaching the writhing mass of tentacles in the waterfall.
Boss: Octomammoth (Octomamm)
The Octomammoth only looks intimidating! With two strong magic users and a strong physical attacker, he should be no match for you.
Rydia probably knows Thunder by this point, but she can do more damage Summoning Chocobo each turn. Have Tellah cast Thunder to exploit Octomammoth's weakness, and heal the party as needed. Don't forget you can heal everyone in the party at once by pressing right while selecting a healing target.
Octomammoth is weak to Dark. You might think that Cecil's Darkness ability can exploit this weakness as well, but despite the name, it only deals non-elemental damage. Just have Cecil attack with his sword.
As you wear down Octomammoth, he loses his tentacles until he has just one left. After you defeat the Octomammoth walk through the waterfall that it had previously been guarding.
Walk around to the northwest, where Damcyan Castle comes into view. Before you get too close, airships fly in and bomb the castle! The party was too late!
Enter the castle anyway, and walk up a few flights of stairs. On the second floor, there is a single, unplundered chest with a Tent. Continue on to the third floor, where you spy a woman lying on the ground. It is Anna, Tellah's daughter. Furious, Tellah attacks the bard standing nearby. That spoony bard!
Anna is hanging on for life, and begs Tellah to understand her love for Edward. Edward explains that Baron's Red Wings, led by Golbez, attacked Damcyan and took its crystal. Anna passes on, and Tellah vows to get his revenge on Golbez, then storms out of the castle. Cecil convinces Edward to join the party to search for the Sand Pearl. Edward says you can find Sand Pearls in the Antlion's Den to the east, and even lets you use his hovercraft.
But before we go save Rosa, let's do a bit of looting, shall we? Head back into the castle, but don't go through the gate. Instead head around to the east and enter the small room - the Damcyan Castle Dungeon. Talk to the guard in front of the switch to open a room containing a secret passage that leads you into the dungeon cells. The chests contain Crossbow, Feathered Cap, and Ruby Ring. Exit the cells and head down the stairs for a whole lot more loot: Potion, Antidote, Eye Drops, Gold Needle, Phoenix Down, and Ether. All but one pot contain treasure too: Holy Arrows x20 and Iron Arrows x10.
If you return to the third floor of the castle, you can chat with a few of the survivors. There are also two magic pots in the east and the west wing. The east pot restores your MP and the west pot restores your HP and removes status effects.
Before you head out, look at the party's equipment. Edward comes equipped with a Bard's Tunic, which has the same stats as Leather Clothing, but also prevents silence. Seeing as he has no magic and his Sing ability is random, it has little use on him, so swap it with Rydia instead. Put him in the back row, because he only has 60 HP right now. You may also wish to head west over the shortcut around the coast and return to Kaipo to restock on items. Now, it is time to head east in your new Hovercraft and enter the Antlion's Den.
Use the hovercraft to fly to the northeast part of the desert, and travel across the shallow water to the other expanse of land. If you see a mountain with a curvy path leading up to it, you've gone too far east. The Antlion's Den is in a mountain range just north of a desert. Save, and head inside.
Antlion's Den B1
Walk down the stairs, then go west, and north under a bridge for a chest with Potion. Then, pass back under the bridge and continue west, taking the stairs up to another chest with Spider Silk. If you're playing the SNES version of the game, you'll have to walk back up to the entrance of the cave and cross the bridge for that chest.
Head south, down a set of stairs, then around to the west and up another set of stairs for a Tent. Just beyond that chest is another, containing a Potion. Go back down the stairs, back to the north. Head east when you come to the staircase again, and continue east until you come to a path under a bridge to the north. The chest there contains Potion. Head south, then go east and up a set of stairs. All the way to the north is a chest with Gold Needle. Go south, and down the stairs to the next floor.
Antlion's Den B2
Go south, down two sets of stairs, and grab the Antarctic Wind from the chest. Continue down the next set of stairs, then go up the other set of stairs immediately to the west and through the door. Either staircase in this room takes you to a chest with Lamia Harp, a good harp for Edward that can cause confusion when used to attack. Exit the room.
From the main room, head west, then north up a long staircase. Continue north, and take the stairs to the next floor. Back on B1, follow the path to the west and go through the door. There is a rest area here, so heal up with a Tent, and save the game. There are three chests in the room as well, with Phoenix Down, Ether, and Emergency Exit. Exit the room, and go back to B2.
Back on B2, head north up a set of stairs, then east, for a chest with Potion. Go back down the stairs, and west across a bridge for Spider Silk. There are two areas that you could explore in this room, to the west and south, but there aren't any hidden items or chests to be found. From the last chest you opened, just go back across the bridge, then south down a set of stairs. Head west, and south down another set of stairs, then through the stairs to the next floor.
Here, simply go south, down the stairs. Heal up before the fourth set of stairs, since you will be facing the owner of the nest soon...
Any time you attack the Antlion with a weapon, it counters with a powerful needle attack. However, Rydia's magic and Edward's songs do not trigger the counterattack. Have Rydia use the Chocobo summon for a heavy-hitting physical strike that Antlion won't counter.
When you have defeated the Antlion, use the Emergency Exit you found earlier, use Rydia's Warp spell, or just walk back out of the Antlion's Den.
Return to Kaipo
Fly the hovercraft west past Damcyan, and continue to the southwest of the desert. Cross the shallow water back to the desert where Kaipo is.
Back in Kaipo, go to the house where Rosa is staying, and use the Desert Pearl on her. When she awakens, she will tell you more about the newly appointed Red Wings captain, Golbez, who appears to be manipulating the king to claim the crystals for himself.
The party will rest for the night, but Edward decides to go for a nighttime walk.
Edward goes outside alone to play some music and mourn the loss of his beloved Anna. His rumination is interrupted by a Sahagin attack! Edward must fight off the Sahagin alone, but the battle is fairly simple. Just attack with the harp, it's impossible to lose this fight.