After you defeat Biting Lizard and receive Undine's magic, you can enter the Underground Palace, which can be reached from the Dwarf Village.
Stock Up on Supplies
Now that you have magic, you should buy Faerie Walnuts. These replenish 50 magic points. Unfortunately, the only way to get them right now is from Neko, who charges twice the normal price.
While in the Dwarf Village, go to Watts and have him upgrade your weapons. He can upgrade any weapon that you have weapon orbs for.
Level Up Magic
You can currently level up your magic spells to level 1. Whenever you seal a mana seed, it increases the level that your magic spells can reach. Since you have only sealed one seed (the Water Seed in the Water Palace) so far, your maximum magic level is 1.
To level up magic, just use the spells until the magic levels up. You can check your progress toward leveling up by going to Primm or Popoi's Weapon/Magic Level menu (it's in the same ring menu as the one where you equip armor) and pressing R to view the magic skill display. The number on the right goes up whenever you use magic. When it reaches 100, your magic levels up.
To level up Primm's magic, have her use Recovery over and over until her magic levels up. Stay at an inn to recharge her magic points when it runs out. For Popoi, just go to where there are enemies and use Freeze or Energy Absorb. Go to an inn when out of MP.
Enter the Underground Palace
The entrance to the Underground Palace is in the area of the Dwarven Village where you fought Tropicallo. If you have trouble finding it, just find the Inn of the Dwarven Village and walk south. The cave entrance is visible below you.
Inside, you find lava blocking the way. Have Popoi use Undine's Freeze spell on the crystal orb to cool the lava. Now you can go north into the palace.
There are goblins guarding the entrance. They can cause Ma Goblins to appear. The regular Goblins are purple, so be sure to attack them first to stop them from making Ma Goblins appear. After defeating them, go through the door.
Up ahead, there is another Goblin that creates Ma Goblins. Get rid of them. The stairs are blocked by a big torch, so you need to go to the bottom right and the bottom left areas. Each area has a switch to step on. There is a bat guarding the bottom-left switch and a slime guarding the bottom-right switch. Once you step on both switches, the torch blocking the stairs disappears. Go up the stairs in the middle of the north wall.
Step on either of the switches here to reveal a bridge. Go north. Follow the path around, fighting some Goblins on the way. When the path is blocked, equip the Whip and stand above the wooden stake, then use the whip on the stake to the left. Continue on the path and go up the stairs.
In the next area, defeat the Goblin and go up through the door. There is another goblin in this area, and two Chess Knights. Go up the stairs past them and defeat the Goblin in the next area, then go up the stairs.
You will reach the area where the Fire Seed should be. Gnome appears and tells you that you can't barge in here. Popoi beats the Gnome up, then Fire Gigas appears.
Fire Gigas can be easy to defeat if you have Popoi cast Freeze as rapidly as possible. As soon as you have finished casting a spell, open the menu to cast the spell again. If you do this, you should be able to defeat Fire Gigas without even needing to replenish your magic, and you shouldn't have to worry too much about Fire Gigas's attacks.
He can split apart into energy balls and regroup elsewhere, and can't be hit while in orb form. He also has a couple of fire magic attacks, although you can prevent these from being cast by casting your own magic as soon as you see him stop to cast the spell.
Get Gnome's Magic
Go north to the next room, then go north to the pedestal. Gnome will grant magic spells to Popoi and Primm.
Seal the Fire Seed
Go up to the Fire Seed on the pedestal and check on it to seal it with the sword. Popoi will also go up to the seed and will regain the lost memories. Popoi asks to be taken to the Upper Land forest.
Leave the Palace
To get out of the underground palace quickly, use the Escape Rope.
Go to Watts and have him upgrade the Axe since you got an axe's orb by defeating Fire Gigas.
Your next destination is the ruins of Pandora, where Elinee sent Dyluck to Thanatos.