I am a fan of using Carbon Copy Cleaner or SuperDuper to get a bootable image to an external firewire (then boot from it just to make sure you are all set) even with the time machine backup available. In fact it allows you to still use "your mac" if you can snag a friends or something for quick work on your principal dataset. Also when the machine comes back, you can instantly plug in boot from external and work, saving the copy back time for after hours.
Then disk utility, repartition and format the disk and reinstall OSx so you are sending a freshly installed mac to them. I have too many accounts and too much cruft, files, etc. that I do not want to make mistakes when sending my machine off.
Again, this may not be the minimalist waay to do it, but it is a framework of a method that has served me well maintaining all sorts of machine (PCs via Ghost or PING, Linux via PING or dd for that matter).
-unixham