A lot depends on the boat. If you're on a cruise ship, or something similarly massive, you'll likely barely even notice the movement. My experience has been on cruisers and destroyers, affectionately called "smallboys" in Navy parlance but still pretty darn large (560 feet, displacement ~9000 tons). It's not too difficult to shave in most conditions - when it's really rough you've got a tough enough time standing up, let alone trying to shave.
The rocking is felt most when seas are "on the beam" - that is, when the direction of the waves' rolling is perpendicular to the direction of the ship's travel - therefore the majority of the rocking is side to side. To effectively deal with this, ideally, shave at a sink where you're facing the bow (forward). lean in, and set your feet wide with your knees flexed a bit. This allows you to absorb the majority of the roll with your legs. You develop a rhythm rather quickly, actually. Important safety note: never let go of the razor at any time during your shave - things tend to slide around some, and an open straight razor is not something you want loose and moving around of its own accord.
Aside from the open ocean, there is very little movement actually felt onboard. For example, we usually spend several months of a deployment in the Persian Gulf, and most days one could shave with a straight without giving it much of a thought. In the Pacific it's a different story. Some days you just have to know when you're overmatched, and break out the Trac II.
On a smaller boat, like a personal sailboat or something, I don't think I would even try it.
I Conquered the 2012 Shave Purchase Sabbatical
It really is all James' fault.
(Okay, maybe Owen had something to do with it as well.)