Head down to the first ship and take out the mini-safe by the ship's wheel, then the three bottles right on the other side of it. Past the star-throwing enemy, use the flotsam in the water to jump across to the next platform, but be careful to move quickly onto and off of the debris that has a spotlight going over it. You can pick up two clue bottles along the way, then be prepared to quickly take out the belly flop enemy at the other side. On this piece of ship, there is a mini-safe and a lone clue bottle by the main mast. When you have everything, hook onto the rigging on the side and climb up to the crow's nest above. From there climb the rope up to plane hanging above.
You'll see that the bottles on the opposite wing's tip are covered by a stationary spotlight, so it's best to go turn off the security before getting them. Head down the fuselage toward the rear of the plane avoiding the four spotlights to break the security siren on the bridge. Come back after getting the bottles and thief walk around the pipe to some more bridges. There are two bottles on the next plane wing, but be careful in this section, because the star-thrower has a very long range. Make sure to time your jump from wing to wing so you don't land right into his throw. After you dispatch him, hook on to the rope and climb over the enemy below and drop down on top of him for an easy kill.
Jump over to the submarine, but watch out for the roving flashlight enemy over there. Sneak up behind him and take him out, then grab the bottles on the far side of the sub. Head off the side of the sub and follow the path around to some more floating debris, this time guarded by a star-thrower. Time you jumps well and go take him out first and come back for the bottles if it's too hard to do all at once. Along with the star-thrower, there is also a belly flop enemy on the last piece of ship. You'll also find the last clue bottles in the mini-safe and one by itself. Climb up the rope to the safe, then use the safe or the other rope on the side to get up to the key and finish the stage.