.. What should I do first?

You need to get another briefing.

Someone can brief you at the place you were briefed before.

Go to the SCUMM Bar.

The cook looks talkative.

Talk to him.

He says you need to go rescue the Governor on Monkey Island.

To do this, he says you need a ship.

Which you can buy at Stan's Previously Owned Vessels.

Getting a Ship

But what do you need to pilot the ship?

A crew.

Your crew must contain three people other than Guybrush.

Getting a Crew