Head to the Palace again. Before going to see the mayor, stop at the Scroll Dealer (left in the main lobby) and buy a Heal Plus Scroll.
Now go see the mayor. You'll learn vBolt, your first Vampire and second achievement.
Go to the equipment shop in Riverside and sell everything except your Chain Mail. Now go to the beach. The Captain's ship is there now.
Get the Apples from the Captain's room.
Now buy 4 Bait from the merchant below deck and 2 Spear from the guy selling weapons.
You'll probably need to fight a few battles before shipping out. You want to be on Level 4. Head to the Haunted Mansion and fight a few battles near the door if needed. Now go back to Riverside and buy some Elixir at a cheap price, but save 200-250 for some Potion Plus which you get Below Deck on the boat.
Talk to the Captain on deck and when he asks, say Head East.