I have never been on a cruise but I have been on ships at night on the Pacific coast. As far as why viewing stars may have been so poor is a few reasons. The first is aerosols, some of it man made some it natural. Typically, winds in the part of the world you were traveling in travel west to east. So all the man-made air pollutants from the US flow out to sea. Mixed in with the pollutants is dust, sand, and sea salts. These can act as catalysts for water vapor to cling to. And since the waters down there tend to be warmer, there is plenty of water vapor aloft. While the vapor aloft may not have been moist enough to create a marine layer (low clouds), the higher the humidity level is, the more difficult it is to see through it. And if there is enough humidity or pollutants in the air, the light pollution from the mainland can sometime affect you even when well offshore.
An experiment you can try to see what I mean is take a fish tank or large clear glass bowl of water. Turn off the lights and shine a light through it straight down. The light should pass through with very little dispersion. Add a bit of milk to cloud it up and dilute it and shine the light through it again and you should see a difference as the light is scattered making the visibility worst. The more milk you add (which is acting like pollutants and increased humidity) the harder it is to see through the bowl and the harder for direct light to pass through.
The best time to attempt to see stars out to sea is in the winter and the further north you are the better. The same can be said for viewing stars on land. Winter is the optimal time of year, and the further north (and higher up you are for that matter) the better. On the summit, star viewing and 130 mile visibilities are common in the winter but once summer rolls in, the viewing cone becomes smaller with 130 mile days happening only once or twice a month.
Since it sounds like you are a cruiser and interested in seeing stars, maybe try a cruise off the Alaskan or Canadian coasts in early spring or late fall to get the star gazing experience you would like. Or if you are even more adventurous, try out a summit Edutrip in the winter to see the stars from New Englands highest peak (http://www.mountwashington.org/education/edutrips/)
Hope this helps-
Staff Meteorologist/Night Observer, KMWN (Mt Washington Obs., NH)