The Underground Palace is found within Dwarf Village.
Kill the Goblins near the door, and then open that door. The stairs straight ahead are blocked by a pot of fire; to get rid of this, take both the left and right path and step on the switch that is at the end.
On your way are two Chess Knights; though they are not as aggressive as the Goblins, they have high speed/evade, so avoiding them is best for now. Go up the stairs and step on any of the two switches to activate the bridge. Continue north, follow the trail, and equip the Whip.
In the next room is a duo of stakes. Whip yourself to the other side, but watch out for the Green Drop that awaits you on the other side-you might want to take care of it before by firing a long-range weapon. Go all the way north from there.
In the next room, go north again, and keep the Sprite alive. Move on, and you will eventually reach the stage room. Gnome is here, but is a little unfriendly, and cowardly runs off once he notices something coming. You will enter a boss battle with Fire Gigas.
After defeating this boss, head north. Here is, besides Gnome, a seed just like in the Water Palace. Talk to Gnome, who in return for getting rid of Fire Gigas bestows his magical abilities upon the girl and the sprite. When you are finished, go to the Earth Seed and gain its powers. Sprite will regain his memory by doing that, and indicates that the Upper Land is his home.
To exit the Underground Palace, you can go by foot or use the Magic Rope to immediately return to the entrance.