After you knock some sense into Santa Claus, he gives you the Fire Seed, which you should take back to the Fire Palace.
Return to Kakkara
There is a Cannon Travel Center in the Ice Country, just south of Santa's House. Use it to return to Kakkara. You will be sent straight to Kakkara Village.
Exit the village, then go south, west, and north. You'll reach the outside of the Fire Palace. Get past the two Sand Stingers. There is a Spider Legs hiding at the base of the stairs. Go up the stairs. Up ahead, there is a Spider Legs hiding between the columns, and a Robin Foot on the ledge. Go north into the palace.
Go into the archway on the left. Follow the path to reach a hot underground room. There are Dark Funks in this room that are vulnerable to Undine spells. Go to the top-right of the room and use the Sylphid Analyzer spell on the crystal orb. It says to use Salamando's magic. Use Exploder. Go up the stairs at the upper-right.
The Red Drops here cause you to become engulfed in flames. Go to the left. There is a shortcut to the entrance if you use the door below the stairs. Otherwise, go up the stairs in the middle.
Go to the left and use Analyzer on the orb. It says to use Salamando. The Fireball spell will work. Go down the bridge that you created. Go east and follow the narrow path northward, then go through the arch up there. You will find a chest that contains 1000 GP. Go back out and go down the path, then go east and up the stairs.
Go all the way to the left and use the stairs there. In the lower room, go up the middle path, then use the path all the way on the right. You will find an Axe's Orb up above. Go back and go up the stairs.
Go to the right, then go down when you can. When you have gone as far south as you can go, go left, then up, then right, and use the stairs there.
Follow the path through this big room. The path is straightforward. You'll encounter a Mad Mallard, some Dark Funks, and some Robin Foots on the way.
In the next room, go up the altar on the left and step on the switch. Go to the right and go down the stairs, then go to the right where you couldn't go before. Use the stairs on the far right.
Go up and use the whip to cross the gap. Go south and use the stairs there. Use the next set of stairs nearby to go to the next room.
Step on the switch to light the torches. A crystal orb appears. Analyze it, then use Freeze on it. Look for the torches that are still lit. Step between them to make stairs appear. Get ready for a boss fight (you might want to cast Thunder Saber on everyone's weapons now) and go up the stairs.
Use Thunderbolt on Minotaur. When his HP gets low, he turns red and moves more quickly. He can use Earth Slide level 7 on you, but you should be okay. If you use magic quickly enough, he might not even have a chance to use it.
After the battle you get a Javelin Orb.
Go north through the door. Use the sword on the Fire Seed to gain its power. Now you can level up your magic to level 4.
Use the Magic Rope (which you can use as many times as you want without it disappearing) to return to the entrance of the Fire Palace. Exit the palace.
Return to Kakkara Village by going south from the fire palace, then east and north twice to the village. Forge your weapons there. Apparently they need a Sea Hare's Tail to restore the water to their village. You can't get one yet, though, so just keep it in mind for later.
Next you should use the Cannon Travel Center to go to the Ice Country to level up your magic. Remember to cast your spells when you are in an area where you are holding weapons, because you earn more magic experience that way.
After you are done leveling up any magic and weapons, you should return to Kakkara Village, then use their Cannon Travel Center to go to The Empire.