To exit the North Palace, go off of the left side or right side of the screen. Then you will be in the overworld.
If you go onto the grass or into a forest or marsh in the overworld, random enemies will appear around you. They will wander around randomly, and if they hit you, Link will appear in a side-scrolling screen where he must fight some enemies.
The action screen that Link ends up in depends on where you are on the map. If Link touched a blob-shaped enemy in the overworld, the action screen will be easier to get through. If he touched a moblin-shaped enemy, the action screen will be more difficult.
You can exit from the action screen by going off of the right or left side of the screen.
If Link is on a dirt path, the action screen from touching an overworld enemy will have no enemies in it. This means that if you trigger some random enemies on the overworld, you can run over to a dirt path to avoid fighting the enemies.
Anyway, your next destination is Rauru Town. If you have never played Zelda II before but you have played Ocarina of Time, you will notice that Rauru is the name of a character in that game. There are other locations in Zelda II that share a name with a character from Ocarina of Time.
To get to Rauru Town, go east from the North Palace, then go northeast along the path, and finally, go south. Rauru Town is there next to a boulder.
To talk to people, just use the attack button while standing near someone.
In town, there is a white house near the entrance where a woman in a red dress is walking around in front. If you talk to her, she will go into her house. Follow her and press up at the door when it is open. She will heal your life to 100%. It seems kind of suspicious, but whatever.... There will be a woman like that in every town.
Next, go left until you reach the next screen. A woman in a purple dress will walk out of a house and walk around in front of the house. Talk to her and follow her into the house. Continue to the right and you will find an old man. He will teach you the Shield spell. When you cast this spell, enemy attacks will only be half as damaging as they were before.
Now you are ready to go to Parapa Desert.