Bloodmoon:An Island to the North

Quick Walkthrough
#Inquire about Solstheim to learn about the island and Fort Frostmoth.
#Travel to Khuul and speak with the Khajiit S'virr on the docks to travel to Solstheim. 
#Speak with Basks-In-The-Sun on the Solstheim docks and be directed to Captain Carius and Carnius Magius. 
#Explore around the area as desired before finding the Captain.

Detailed Walkthrough
Rumors of an Island
When you first run the Bloodmoon expansion, there will not immediately be any obvious differences. You can see the new island of Solstheim on your world map (scroll by holding down the left-mouse button and dragging). If you ask around about Solstheim, you'll hear rumors of an island to the north of Vvardenfell named Solstheim, and about an Imperial fort named Fort Frostmoth. If you inquire a bit more, you'll also learn that there is now boat transport to the island from Khuul.

Traveling to Solstheim
To reach the new island, you can either take a long swim (or walk with Water Walking or a flight with Levitate), or you can simply travel to Khuul and speak with the Khajiit S'virr on the docks. Select the travel option as with any other NPC who offers travel options, and select the one destination, Fort Frostmoth.

Arriving on the Island
The trip is short and uneventful, and you arrive on the docks at Fort Frostmoth. Speak with the Argonian Basks-In-The-Sun on the docks who will welcome you to the island and suggests that you speak with Captain Falx Carius in the General Quarters at the fort and with Carnius Magius at the Imperial Cult Shrine. You arrived at the docks on the southern end of the island and the fort is just in front of you. The Argonian will also give you some basic info on the island and warns you about the bears and wolves found about. Basks-In-The-Sun offers travel back to Khuul as well as to Raven Rock, a harbor west of the fort where the Empire wishes to build a new mining colony.

Exploring
Take your time and explore the area around the dock and the fort itself to become familiar with it. The three people near the dock have nothing useful to say or do, yet anyway. Likewise, the guards in the fort are all tight-lipped. The fort itself holds a few areas of interest such as the Prison, Armory, Imperial Cult Shrine and the General Quarters. The prison is small and empty but does contain an Evidence Chest should you ever need to reacquire certain items. The General Quarters leads to the Upper Quarters as well as Captain Carius' chambers and a supply room. Carnius Magius can be found upstairs in the Shrine area. Most people will not speak regularly to you until you visit the Captain or Magius.

Notes
As usual, be careful when poking about in the various crates, chests, barrels, sacks, etc... Sometimes you can take things without people minding, and other times they will object. 
If you cannot seem to get the required information out of someone, try raising their disposition by persuasion or bribery. Some NPCs won't divulge important information unless they really like you.
Captain Carius starts you on the Bloodmoon Main Quest.  Carnius Magius starts you on the independent side quests for the East Empire Company; if you do not join this faction, you will skip a lot of the things to do on Solstheim.

Quest Stages