Great Bay Coast
After you get Epona back, gallop towards the western part of Termina and jump over the barriers to reach the beach. Get in the Fisherman's Hut on the left and speak with the man along with the seahorse (with Z lock). The fisherman says that the seawater got warmer and murky lately, and that he saw a Zora floating lifelessly, whereas the seahorse wants to go back to the waters near Pinnacle Rock. The fisherman proposes to give you the seahorse if you can get him a picture of female pirates. Get out, swim towards the house on stilts and check the Owl Statue. Climb the ladder, get inside the Marine Research Lab and talk to the scientist, who tells you about the hatch of Zora eggs and the abnormal water temperature. Next, get out and pop Tingle's balloon just above to buy the Great Bay map for 20 rupees.
Now look for seagulls which are flying in circle and look underneath them to find a Zora who almost drowned. Grab him and pull or push him towards the sea bank, then speak to him. He's Mikau of the Zora people. Listen to him so he tells you about a Zora girl who laid some strange eggs, stolen by Gerudo Pirates, and who lost her voice. Play the Song of Healing to heal his soul and Mikau will disappear and leave you the Zora Mask. Wear this mask and look at Mikau's remains to learn about your new abilities. Head south, towards the Zora Hall.
Zora Cape
Swim towards west, dive to walk underwater, punch the big monster trying to suck you up, then enter the Zora Hall. Talk with the Zoras you are meeting, then take the path to the east. There is a shop selling shields, red potions and arrows. Go left (to the north) to get out. Talk to Lulu as Zora Link, then activate the Owl Statue.
To go on with your quest, one mask will be really useful, but you can also make it without it. To get it, soar to Clock Town, go to the Western District, enter the Trading Post and buy a red potion for 30 rupees (they are cheaper than in the Zora Hall).
N64: Leave Clock Town, call Epona and gallop towards east. Jump over the barriers, then look for a rock circle on the right. Get off and use the Lens of Truth to find a lost soldier. Talk to him and give him the red potion. As a reward, he will give you the Stone Mask and Shiro will be added to your notebook.
Great Bay Coast
Soar to the Great Bay Coast, then swim straight to the north and a little bit eastward. Make sure you keep some magic as you will need some later! In front of the rocks, dive to the bottom of the sea and look at the skulls drawn on planks. Swim at full speed (creating a barrier) towards the second skull from the left to break the planks and find a passage. Follow this new path, then get out of the water and discover the Pirates' Fortress.