It has been suggested that this page be merged into The Legend of Zelda: Phantom Hourglass/Sidequests.
You may discuss this on the page's talk page.
This side quest is available from once you have the ability to navigate through the fog on the northwestern sea.
Uncharted island is, as the name suggest, an uncharted island found in the northwestern sea. It is discoverable with a map found in the hideout in the cave on Molida Island. Or, you can just look at the screenshot to the right and see where it is. When you get close enough to the island, Linebeck will see it and register it on your Sea Chart.
Once there, you'll notice there is no map. Go around the island, and draw it. If you did it correctly, it should look much like a whale. After that, you will need to get into the golden king's palace.