Due south of the first palace, you'll find a road leading to a small forest. (One of the road squares is a battle square with numerous pits and bubbles. Shouldn't be a problem.) Go to the patch of grass in the middle of the woods. The Heart Container will be to your right, guarded by an Orange Goriya. (I highly advise dealing with the Goriya first - the Container will heal you anyways!)

After you get the Hammer, Go to the road from which you'd head west for the second palace. Instead of going west, though, walk east. Whack the rock guarding the cave, and a Heart Container will be at the end.

When you get the Boots, walk into the sea as you would to get to the fifth palace. After some walking, however, move north four spaces, then continue east. You'll come across a "battle" square with a mountain holding another Heart Container.

Search the beach around the sixth palace, around the south-east corner of the world. The final Heart will be in that area.