While boating, you can't always stop and heal up. If the sea isn't too deep you can anchor after a battle. This is after battles 4, 5, 6, 9 and after battle 10 you automatically stop before the boss.
The first time you stop (I recommend after battle 4), walk up to the plank on the side of the boat and go fishing.
Do this 4 times (just press up after each time) and you'll find a special item and be awarded your next achievement.
Before you reach the boss, make sure you have a healthy supply of Potion Plus and Elixir.
After fighting the boss, you'll end up on the Eastern beach. There are 3 merchants there. Buy everything they're selling and sell whatever equipment you can.
The Rune you got from the sea boss tells you the directions you must go in the desert (North, North, West, North, East, East, North.)
Go sleep below deck before heading out to the desert.