After you defeat Spikey Tiger and Elinee gives up her evil ways, Luka summons you to the Water Palace.
Reach the Water Palace
From the door into Elinee's castle, go around to the entrance of the castle and exit south. Go down the stairs near the warp point, then go to the southeast corner of this area and use the warp point. Go down the stairs, then go east and up the stairs. Equip the whip and stand above the wooden stake. Use the whip on the stake across the gap. You will be pulled over. Go south and use the warp point.
Go east and north to reach the Water Palace. Go inside and talk to Luka. She asks you to check on Undine, who lives behind the waterfall east of the Water Palace.
Exit the Water Palace and walk east through the water. Kill the Iffish swiming around in the next area. Then go into the cave behind the waterfall. There are more Iffish in this area. Kill them, then use the northwest exit.
In the next screen, a monster called Tonpole pops out of an egg. Keep your distance and attack it. Once it is defeated, it transforms into Biting Lizard.
Biting Lizard can grab you and your allies with its tongue and chew you to inflict damage damage, so don't stand directly in front of it. Try to use long-range weapons. The closer you stand to Biting Lizard, the more it moves around and attacks. Set your allies' action grids to keep away but attack.
When Biting Lizard dies, use the exit that opens in the north wall. Go up and talk to Undine, who gives Primm some recovery and defense magic, and gives Popoi attack magic. She doesn't give Randi any magic because the Mana Sword will one day be more powerful than any magic. Primm can cast temporary ice power on your weapons. Undine gives you the Pole Dart.
Now that you have Ice Magic, you should go back to Gaia's Navel, where you can go to the Underground Palace from the Dwarven Village and use Undine's Magic to open the sealed entrance.