How to restore a late 2009 iMac after disk replacement
If you have some extra disk space to spare, I would recommend you to make an additional backup with SuperDuper (free for basic functionality, which is all you need in this case!):

You will create a bootable backup, from which you can then boot after you get the repaired Mac back. Test this backup by booting from it once (important) and play around a bit to see if everything feels as it should (improves gut feeling).

Then, you would use SuperDuper, which obviously also is on the backup you have just booted from, and use it to "backup" back to your freshly installed, empty hard drive.

UPDATE: To create the a recovery partition, you can use this useful hint from How can I create or recreate a Lion recovery partition?.

Upsides of this method: You can immediately boot from your external disk, where the bootable backup sits, and you do not have to freshly install Lion, then upgrade to Mountain Lion, and then restore from the Time Machine backup. Hope this helps!