If you kill the dragon (in human form) in the Maxos Temple, the gateway to the Island will appear. Speak with the ghosts there to find out how.

After you go to the Island, you will be able to go the the fjords.