How do I backup Mac Server? It sounds like Time Machine doesn't backup everything on Mac Server:
http://derflounder.wordpress.com/2010/03/02/restoring-mac-os-x-server-from-time-machine/

So what options do I have? Ideally I'd like a backup that I can restore on another Mac Mini and have it up and running instantly. Carbon Copy Cloner sounds like it should work, but I didn't see anything on their site that said it would definitely backup Mac Server (or I missed it).

Does anyone have a recommendation on what to do?
Your primary option is to test your restore with live data so you can see all the things your server setup does that isn't covered by a Time Machine.

You'll also want to get a tool like Bender to handle exporting and importing settings on the server.app itself.



Ideally, you have a setup document where you recorded each and every thing you configured since that will be your checklist that everything is covered. 


Did you set up alternate data location for some of the services?
Did you "correct" any dot files for users and run any terminal commands?
Do you have any launchd tasks that are not packaged (I often make routing and other changes that run to set static routes, roll over application log files, etc...)


Server is a different beast and you can and will set up many large databases - some of which need to be archived and then restored later like mail, web, LDAP. As your server grows, you will come to think of each data as separate since backing them all up with the same frequency or mechanism isn't a good solution technically. Time Machine is a starting point, not an end point and using mirror technology like Carbon Copy Cloner or SuperDuper! isn't usually the answer since it often takes a day or two to restore terabytes of data when you can instead have that data on a storage appliance and just use your OS and configuration backups to save the glue and code and tools - not the product.