You'll actually get the quests for the pirate ship early off, but you won't be able to complete one of them until after you kill Wortten. The quests are fairly simple, and once you finish them, you'll be able to use the Pirate Ship to get to the North Pole and the other islands. The three quests you need to complete are:
Lemon - In order to prevent scurvy on the high seas, you will need some lemons. They can be found in Ima Strunken's farm. You will need to separate Strunken and his wife, since Strunken will not let you have any. Just keep selecting the first dialog option and you'll eventually lead them to get divorced. After he leaves, go back to Ima and ask her for the lemons. She'll let you have them, and after you pick them up, return them to Captain Taint.
Keys to the Ship - To get the keys, you'll need to kill Plaid Pete who is located in the cave west of Scurvyville. The cave does not have the cave icon on the map, but instead a skull. Once again, use the tactics you've used before on bosses and he'll be a piece of cake. His 'special ability' is to pour liquor on you and get you drunk. You'll know when you get drunk since the screen will start moving and pink monsters will appear. Kill all the monsters and you'll return to normal.
Rum - To get the rum, you'll need to go to the Haunted Crotch in Strumfuquel. The owner is Grimtub who will tell you that Wortten stole his liquor license. Kill Wortten using the technique in "To Serve Man" and you obtain the license. Return to Grimtub and then buy the rum.
Once you've done these three quests, return back to Captain Taint and he'll say that you're all set. Go straight until you reach the pirate ship and the achievement will be yours.