What would be the best way to start writing a script to automatically run a bitcoind server on an Ubuntu startup, make regular backups and restart from a backup on error. Would this normally be done through a cron job?
Upstart is the preferred method, have it launch your mining program on boot and respawn the program if it dies.
Checking if it's working is another matter, it requires a more meta approach. I would suggest you start another script that queries bitcoind via the command line, parses the response, and kills the process if it's not mining. Upstart will see that the process is gone and spawn a new one.
If you run into problems (overclocked GPU's are mighty unstable!) you might even want to log the number of times you have killed it and reboot the server after X kills in Y minutes.