To reach Parapa Palace, first you must go north from Rauru Town. You can get a P-Bag if you go north from Rauru Town, then northwest and into the single square of forest along the path. A P-Bag is a points bag. It increases your experience points. However, you might want to leave the P-Bag until later, because if you lose all of your lives, you lose all of your experience points. This is more of a problem if you need a large number of points before leveling up, but at this point you will probably level up as soon as you collect the P-Bag in the forest. It's up to you.

Anyway, if you keep going northwest from that patch of forest, you will reach a town, but you don't need to go there yet.

Instead, go northeast from Rauru Town and into the forest. There is a cave opening just past the forest. If you get hurt in a random enemy encounter before you reach the cave, you might want to go back to Rauru Town and heal up. When you are ready, go into the cave.

The cave is dark, and there is an invisible enemy just past the second bump in the floor. If you have full energy, you can crouch behind the second bump and shoot a sword beam to kill the enemy. If you don't have full energy, try to look at the ground, because you can see some slight movement of the enemy as it moves around. Then jump down and kill the enemy before it can reach you. Be careful, because it dashes toward you when your feet are on the same level as it.

Keep going and you will exit the cave.

You are now in the desert. If an enemy attacks, be careful to block the flying rocks with your shield. Hit the tall worms once to make them shrink, then hit them while they're small to kill them.

Now, you can get your first heart container. If you go southeast from the cave, you eventually reach a dirt path. Follow it and you will reach an action screen where you are on a bridge, and a bunch of poisonous bubbles keep floating up from below. Be very careful to look before you leap, because if you hit a bubble as you jump over a gap, you could fall to your death and lose a life.

Once you get past this action screen, go to the center grass square that is surrounded by forest. You will discover a heart container in the action screen here. There is also a Goriya. Keep an eye on where it's about to throw its boomerang. If it holds the boomerang down low, crouch to block it with your shield. If it holds the boomerang up high, stand up to block it with your shield. This isn't a fool-proof strategy, but it should keep you from getting too beaten up while you get used to the Goriya's movements and get better at blocking those boomerangs.

Once you get the heart container, exit the action screen and head north. You will have to head back over that dangerous bridge of bubbles, and then you will be back in the desert.

Head northeast along the coast and you will reach the first palace: Parapa Palace.