We actually did it last summer, from Noudhibou to Choum, with two 2wd's (Mercedes 200D).
We just asked the clerk at the passenger terminal, and he pointed us to some big depot, near the railway. They told us to return next morning for the big boss (nice guy) to be available. It took some bargaining with him, and in the end we had to buy the whole carriage for 180 euro (if memory serves me correctly).
Next, we had to wait all day at the marshalling yard before they were ready loading all their stuff like potatoes on board. We set off at night and woke up next day day half an hour from Choum, where two guys helped us get the cars of the carriage in the middle of the dessert. The ride was very shaky. Fortunately, they secured everything pretty well...
I imagine it would be more difficult to arrange the other way around, as the guys in choum seem to have less resources in terms of equipment and such.
There's no such thing as reservations or tickets and if you're lucky like us, you can just 'check in' in the morning and leave whenever they're ready to go!
All in all, I thought it went pretty smooth for a first try. Good luck!