You will find the Pirate ship with the key to the Mermaid Island gate off the northeast corner of Cuck Island, the first island that you visited. The layout of this ship will be slightly different than the previous two that you encountered. Additionally, you will be required to defeat 25 pirates before you are granted entrance to fight the captain. Once you obtain the key from the captain, sail due west as far as you are permitted to travel, then sail south until the island comes into view if it's not already. The entrance is on the east coast.
You start off along the east coast of the island. After traveling one screen south and one screen west, you will meet a man (shown to the right) who will inform you of a danger to be aware of on this island: you can fall in the water. And falling in the water comes at a very hefty cost, 3000 of your health points. You must avoid falling in the water at all costs. You will encounter wooden planks that float on water which you must jump to. You will also encounter gray planks which periodically dip underwater before resurfacing, so you must time your jumps across them carefully.
There isn't much important to find on the southern end of the island; exploring this area will only net you some treasure chests which contain food or a POW icon. There are a number of chests in the north east part of the island as well, including one room above the entrance which contains four 600 health point hearts, and a fifth one in the room above, for a total of 3000 extra points.
Aside from a couple of pirates that roam the island, you will encounter a few fishy enemy types, including the Crush Fish which likes to ram into its prey while jumping out of water and across bridges, and the Kraken which sticks its head above water just long enough to spray the nearby area with ink. Since they sit in water, your rocks will not reach them and you cannot kill them. You may also encounter single tentacles. Only the "heads" of the tentacles can damage you (you can safely pass through the stalks) and if you hit them with a rock, they will become temporarily immobilized.
The boss of Mermaid Island is a set of tentacles. A pair of them will rise up from the bottom of the screen, one on the left and one on the right. It takes two hits from rocks to defeat them, and cause another tentacle to rise in its place. When four tentacles have been defeated on either side, the bridge at the top will be completed, giving you access to the screen above where you will discover the triangle tablet waiting to be collected. Additionally, the bridge one screen over to the right will also be completed. If you cross over it, you will find a patch of rocks. Underneath one of them is a hole that will instantly transport you back to the entrance gate of the island.