After the Island Palace, go back to the cave on the Island and then go north to Mido Town (or you could try going west so you end up on the dirt path and become safe from enemies temporarily.) Next to Mido Town in the overworld there is a dock. Step on the dock and you will automatically ride the raft across the ocean to eastern Hyrule.
When you land on the other continent, you will land near a single patch of forest. There is a P-Bag there. To the south you will see a lake surrounded with forest. In the western part of the forest, there is a patch of forest where you will find a fairy.
To the east from the lake and the single patch of forest, you will find a dirt path leading from a town to a cave. First, go to the town. This is Nabooru Town.
In the second section of town, there is a thirsty woman in a red dress walking around in front of her house. Check on the fountain to the left of her house to get some water, then go talk to her. She will let you inside, where you will find an old wise man in the basement who will teach you the Fire spell. This spell is the only way to damage Tektites, Scorpions, and a few other types of enemies.
There is a house in Nabooru where a red Ache is hanging from the ceiling. If you use the Jump spell and talk to it, it says "..." but if you talk to it several times, it eventually tells you about a heart container in the ocean.
When you exit Nabooru, go south and go into the cave southeast of town. There is a 500 point P-Bag in here, beyond some Tektites and a Scorpion.
You can get an additional P-Bag if you go outside and break the boulder to the east and then walk along the coast.
Anyway, go back to Nabooru to heal up, and then head north into the cave. Your next destination is Darunia Town.