Go to the western side where Captain Hanty is. There will be two Suspicious Men there. One of them can clear your criminal records for a price; that is not the right person. (You can tell it's the wrong person if the talk dialogue has an option for "the price on your head".) If you try to get information from that person, he will swindle you with false information and disappear forever. You need to talk to the other Suspicious Man (the talk dialogue does not have "the price on your head") and ask about the Governer's castle. He will ask for $5000 gold. You can get him to do it for $2500. With high Persuade (~55) he do it for $1000. Be ready because he will send you to the Sunken Island as soon as you pay him.