Watch a bunch of pirate movies and take notes. Ships have anchors and ropes that are likely to provide an easy entrance to climbing creatures, and they can always use rope and grapples (giving them a Climb DC of 0 and the ability to take 10 and scale the side of the ship with an accelerated climb).
Ships at sea tend to rock, so it's they're unlikely to notice the boat pitching with the climber's weight unless its a really small boat. The ocean tends to make noise, so I'd give characters a penalty to listen checks. Spot checks are only really going to work for the guy in the crows nest and people standing by the appropriate railing.
You can even allow creatures with a swim speed to make jump checks out of the water, probably a running jump since swimming allows them something of a run-up. With a 60 ft. movement the sauhagin can get a +12 bonus to their running (swimming) Jump and clear a fair height. Taking 10 they have a fair chance of clearing 20 feet. Making a roll, they have a chance of getting even higher.
If your players are still complaining after all that, let the acquatic sahuagin trail them into the open ocean and dissable the ships rudder without coming to the surface. After that, they can let the crew starve of scuttle the hull at their leisure, all without coming up to draw breath. After they've had to swimg 20 miles back to land, fighting sahuagin the entire way, the players may be a little less chagrined by on-ship ambushes.
