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, and there is no way to leave other than with the Town Portal spell or by making it through the tunnel.