The basic TimeMachine recovery procedure boils down to:
1) boot from Recovery/Installation media
2) make use of the Disk Utility (I recall under the tools menu option of the installation USB/DVDs) to format/partition the new disk
3) Then select/choose the Restore/transfer option where you can then select the TimeMachine (Or Migration Assistant) to restore from.
The problems I don't have an answer to as I've never done that in my setups:
a) recovery of the Recovery partition... I usually were doing "upgrades", thus I did fresh installs, and then I restored the TimeMachine specific files, or I used the "Migration Assistant" to restore the applications/users as need be
b) You didn't specify the version, which might mean different issues w.r.t. the medium, ie. USB/DVD/etc. Creating a USB boot image is outside the scope of this question and answer ;)