From Parapa Palace, which is the first palace you encounter, head South. You’ll pass a side scrolling scene where you’ll have to avoid bubbles, and jump from ledge to ledge. You’ll come upon a small forest area. Head to the center of the hedges to the grass area. You’ll encounter an Orange Goriya. Take care of him first, because once you defeat him, you’ll gain the first heart container, which will heal you.
East of Midoro Swamp
After getting the hammer from the Death Mountain Maze, head back toward the swamp, where the second palace was located. Once you reach the swamp, follow the road East until you find yourself blocked by a boulder. Head North, following the road until you see a boulder to the East blocking a cave. Go break the boulder and follow the cave inside to find the second heart container.
The Water Palace
Once you have the boots with the great ability to walk on water, head toward The Water Palace. As you’re walking to great distance across the water, head North about mid path and then head to the East. You’ll find yourself on a side scrolling scene with the third heart container.
East of Three-Eye Rock
By the rocks of the Hidden Three-Eyed Palace, align yourself with the rock and walk straight to the East until you hit the water. Follow the beach North-east and you’ll find yourself with the fourth heart container sooner than you know.