I actually had this happen to me last year! About 6 months before the HD went belly up, I'd purchased a Airport Express with the internal Time Machine HD. I bought a 1 GB Samsung SSD to replace the old HD. I got it all mounted up, fired up the Mac and the system recognized that the HD had nothing on it and reverted over to the Time Machine. It asked me if I wanted to load up the Time Machine data on the SSD and away we go. (it was something like that, basically it was really easy) My memory isn't perfect on this but I do remember it was amazingly easy to get back up and running.
Let me tell you, if you EVER have to replace a hard drive, those SSD units are magical. I can't believe how much faster my old Mac is with that solid state unit over the old spinning hard drive.