By train
If you thought the airline network was a dog's breakfast, you'll love the train system. Describing Cambodia's rail network as antiquated is generous in the extreme. Originally there were two lines, Phnom Penh to Sihanoukville and Phnom Penh to Battambang. As far as we're aware the Sihanoukville line doesn't run anymore. The Battambang train runs once a week, with the trip taking anywhere from 18 to 24 hours. It departs on Phnom Penh on the Saturday, returning the following day. Many foreign passengers go for the ride, but get bored and jump off after one leg (for example at Pursat if coming from Battambang). Fares are nominal.
The train system shouldn't really be taken seriously, but for novelty value (you can easily sit on the roof of the car should you wish) it is unbeatable.