Head to Windhelm and search for the proper ship in the docks. You can head there using fast travel or on foot, which you should of course know very well of. After getting there, head to meet with captain Gjolund Salt-Sage - he can be found on the first boat from the shore (as seen in the above screenshot). Speak with him to learn that he indeed took two foreigners with him lately and that... he never wants to return to Solstheim again.
You can make the captain listen to you in three ways. You can use Persuade, Intimidate or bribe him (which will cost you 500 gold). Regardless of your choice, the end result will be the same and you will end up in the city of Raven Rock. The main part of the new adventure will begin here.