I've gone overland the other way SGN-PNH and there are a fair number of bus, minibus options for the trip. It takes a while mostly because of the bureaucracy at the border crossing, but it's otherwise not the toughest overland trip (its easier than BKK-REP-PNH overland!) I don't know about the boat option, you could check that out too once you get there.
Make sure your Vietnamese visa is in order, and check local conditions before departing for weather, etc.
The motorcycle option is a great one as well-- but imho, Cambodia is not the place to LEARN to ride a motorcycle. If you're experienced, go for it.
If you decide to fly, unless its in the middle of Tet or something, you should be able to just get tickets when you get there so you could play it by ear.
Michael -- welcome to FT! You're the first FTer I've seen actually from Cambodia.