After sealing the Mana Seed in the Water Palace, Luka tells you to go south through Pandora to reach Gaia's Navel and find the Underground Palace.
Go to Pandora
Go south from the Water Palace. If you talked to the soldiers in front of the Water Palace until they left, some goblins will capture you along the way. A mysterious girl will rescue you and then run away. If you didn't talk to the soldiers until they left, then you don't encounter goblins at all.
Go east and then go south when you see the sign that points south to Pandora. Go south into town. Everyone in Pandora seems sad and reluctant to speak.
Get Primm
If you were captured by goblins earlier, go to the second floor of the castle. The path to the castle is in the northeast corner of Pandora. On the second floor of the castle, you will encounter the girl who rescued you. She will insist on joining you. Her default name is Purim. Some sources spell it Primm.
If you did not get captured by goblins, the girl will simply run away and won't join you until later.
Set Up Primm's Strategy
If you're playing solo, the other characters in your party can attack the enemies around you or stay back to defend themselves. You can change your party members' strategy by pressing Y to open the menu, pressing X to switch to the other party member, pressing up or down until you reach the menu that lists Level, Act, Edit, Equip, Stat, and a target. Choose Act (Action Grid). The closer to the top the character is, the more likely he or she will be to approach the enemy. The closer to the left the character is, the more likely he or she will be to attack the enemy instead of staying on the defensive.
After choosing the character's strategy, you are prompted to choose what level that character should keep his or her gauge at. If you hold the weapon button, you charge the weapon to its maximum level. Each time it goes up a level, its attack becomes more powerful. You can tell the character's AI to charge up to a specific level or just stay at 0. The maximum number here depends on the level of the weapon that the character is holding right now.
If you want to switch the leader of the party, press select. You can control Primm with the controller instead of Randi if you choose.
Go to Gaia's Navel
When you're ready, use the west exit from Pandora to continue your journey. On the way, you will pass by Kippo village. You can buy better armor there, so do that.
Detour to the Haunted Forest
Then continue north to get to Gaia's Navel. Primm won't be willing to go to Gaia's Navel. If you go in, Primm will part ways with you. This is not recommended, because you will have to fight a difficult battle to get her back.
Instead, go into the Haunted Forest to the north. Go through the forest. You'll find Neko there. Go east from Neko, up the stairs, go west and step on the warp spot. Go southwest from the warp spot and you will find some skull statues. Try cutting them down and the girl will agree to go to Gaia's Navel since you can't get any farther without an axe.
Go into the Gaia's Navel Cave
Go back the way that you came to return to the Gaia's Navel area. Go down the stairs in the northwest part of the area. Follow the path from there until you see a small hole in the wall with water flowing out. Walk through that hole and go to the left. The path from here is straightforward until you reach two cave openings. The one on the right leads to a dead end where you can meet Neko and buy some overpriced stuff. You don't really need to buy anything from Neko at this point.
Back outside, go into the cave entrance on the left. In the cave, the bats can cast Balloon on you, which freezes you for a few seconds. There are also green slimes, which can duplicate themselves, so try to get rid of them quickly.
From the cave entrance, go north through a door, then go north to find some stairs leading down. Your path is blocked by lava. Go up the stairs to the left, then go into the cave entrance on the other side. Hit the skull switch with your weapon. Exit this room to find that the water that had been in this room has been poured over the lava, cooling it so you can safely walk over it.
Go to the right and go down the stairs, and continue down past where the lava was. There is a door in the wall just south of the stairs. Go through it.
In this room, don't go down the stairs in the south wall yet. Instead, go to the left, up the stairs, and into the cave entrance up above. In this room you will find a couple of goblins and a chest. The chest contains the very useful Magic Rope, which lets you escape from some dungeons. It does not disappear after use.
Exit the room where you got the magic rope, then go south until you find the stairs in the south wall. Go down those stairs.
There is some water to the right, and also a path, but the path is a dead end. Go south into another area where there is more water on the right. Head southwest, following the path until you cross the water. Go north along a narrow passage between the water and the wall. Go down the stairs that you find here.
Go east from here. You will pass by a ledge that you can't reach. Go up the stairs on the right side of the room. In the next area, look for the skull switch on the wall. Activate it with your weapon, then go back down the stairs. You can now reach the ledge that you couldn't go into before. You will find yourself in the Dwarf Village.