NavList:

For the purpose of celestial navigation, I assume.  Thus you're really interested in UT1, the Earth rotation angle, rather than uniform time per se.  You can have an excellent uniform timekeeper (an atomic clock of some type let's say), but your UT1 prediction will eventually go stale in a few years or decades.

But aside from that, for the timekeeper / chronometer, there are the usual issues of accuracy, power budget, and cost. 

At a power budget of microwatts, the high-accuracy thermocompensated quartz wristwatches are doing reasonably well.  These are effectively micropower TCXOs using two low-frequency crystals in a self-calibrating arrangement.  They are limited by rather high aging (on the order of a few ppm per year).  I'd like to see this type of wristwatch be disciplined by periodic checks against a stable MEMS reference, some of which have remarkably low aging.  The periodic checks would be so seldom (once per day let's say) that the power increase amortized over a long period would be negligible.

At milliwatts, probably a mass-market TCXO (temperature-compensated crystal oscillator) is your best bet.  These can be pretty good for stability (~0.1 ppm over temp) and low cost (~$5).  They are better than wristwatches but would quickly run down a wristwatch battery.

At a few watts, what you want is an OCXO, an oven-controlled crystal oscillator.  This is a crystal oscillator held at a certain temperature by a small heater.  The temperature is carefully chosen to be at the inflection point of the crystal's temperature dependence, so the tiny residual temperature fluctuations of the oven affect the crystal very little.  Accuracy, stability, aging are all maybe 50x better than TCXO.  Cost is perhaps $50 on the surplus market, even for premium features like double oven or SC cut.  New they would be several hundred dollars.

If you can afford five or ten watts, an OCXO disciplined by a rubidium vapor cell will offer better long-term stability (lower aging) by a large factor, maybe another factor of 50 better than even an excellent plain OCXO.  These are available on eBay as surplus for around $200.

I'm not sure it makes sense to go beyond rubidium because of the UT1 limitation mentioned above, but if you really want better uniform time, you will need a cesium clock to avoid certain rubidium aging mechanisms.  There are small cesium clocks available from Symmetricom for $2k or so (and they are under 1 watt I believe; quite amazing).  A lab-quality cesium like the 5071A is much more expensive ($100k?) and probably past the reasonable point of hosting in a marine environment, unless it's an aircraft carrier.  Beyond the lab cesiums are things like cesium fountains and optical trapped-ion clocks.

As a fun exercise, I wonder whether an OCXO could be ovenized by the ocean.  That would really reduce its power footprint, from watts to milliwatts.  Dangle it from a ~100 meter tether.  You'd need a special crystal with turnover temp at 15 degrees C or thereabouts.  One would extend or retract the tether to keep the temperature at the crystal's sweet spot.

The time-nuts mailing list might be a good source of advice.