First of all, if you're heading to the ice cave from Crescent lake you don't need a ship, you need the canoe, which you can't misplace. Secondly, if you lost your ship, wander around the coast, check the docks (Far north east) and the places where the rivers terminate. If in doubt as to where those are, refer to a world map.