Destination Skellige - Novigrad
This quest is given to you very early on in the game after completing the Imperial Audience Story Quest. In Novigrad there will be three locations marked on your map, all three captains will refuse to take you to Skellige but the one at the southern most quest marker on your map using a spyglass will direct you to a captain who will.
He'll direct you to The Golden Sturgeon where you will find captain Wolverstone drinking at the bar. Speak to him and agree to pay him 1000 Crowns for a trip to Skellige. If you're worried about the cost, fret not, we'll get the Crowns back soon enough. Once you pay him all you need to do is speak with him to set sail.
After a cutscene you'll awaken on the boat, under attack by Skellige Pirates. Defeat most of them for another cutscene after which you'll wake up on the beach of Skellige. Search the entire area before leaving as you'll find numerous Crafting Recipes as well as a bunch of other goodies including a Place of Power. To the south on the small peninsula you'll find the captain's corpse which has your 1000 Crowns (pictured below).
When you've gathered all there is head north to Kaer Trolde where you will be treated to a cutscene followed by the completion of this quest. After the cutscene in town you'll receive the next Story Quest, The King is Dead - Long Live the King!