Locate Sealed Cave
To the south in the underground is a cave which is completely surrounded, and can only be entered from above. This is the sealed cave, so land the airship and enter the cave.
Note: if you already obtained the Dark Crystal by having Rydia cast Warp in the Dwarven Castle throne room, you do not have to complete the Sealed Cave. This only works in the SNES version.
It would be prudent to carry at least 15+ Phoenix Down/Life items into this dungeon, just in case.
Enter the Cave
When you enter the cave, approach the door. Use the Luca key on it and it will be unsealed. In the next room follow the path all the way around the room, until you reach the second door in the room. Like almost every door in the cave, this door is a trap, and you will have to fight it in order to pass through.
TrapDoors attack using a combination Search, then Disrupt. They will first use Search, then about 2 rounds later they will use Disrupt which will automatically kill that member of your party. If you have not defeated the TrapDoor past a certain point, it will change into another monster, which you will have to defeat also in order to pass.
In the next room you can ignore all the doors, and continue into the next room. In this room, go to the right, then up and you will reach a long stretch with many trap doors. None of them are necessary to continue, but some contain chests, and one has a save point. Continue past them to the door at the bottom left of the room to continue through the cave.
The next two rooms are small, continue through them, ignoring the trap door in the second room. In the large room you next reach, cross the rope in the center of the room, then go to the left and down the staircase.
Use the savepoint in the next room, then continue on. The next room is a large circle. Ignore the ropes and go all the way around the edge and down the stairs in the middle. In this room you will see a bridge with one final trap door. Enter it and defeat it.
Retrieve the crystal, and attempt to leave the cave. When you try to cross the bridge, you will be interrupted by another trap. This one is a Wall that will move toward you as you attack, killing you if it gets too close. You must defeat it as quickly as possible. Cast Berserk on Cecil and Edge (and maybe Kain), and have Rydia cast Virus/Bio.
Now you can leave the cave (Exit and Warp will not work so you have to walk). Just as you are about to exit the cave, Kain will steal the crystal and leave your party. After this occurs, leave the cave and fly back to the Gnome City.
First, go visit the king, and he will tell you that you must return to Mysidia to get the ship necessary to fly to the moon. Cid will enter the room then attach a drill to your airship. Finally, get in the airship and go to the circle in the northeast part of the underground, place your airship above it, then press the button to land, and you will drill your way out of the underground.
This would be a good point to attempt the Sylph Cave.