The hardware isn't *too* complicated. You will need to program the stamp to do what you want, of course. If you get the serial basic stamp, you could write a program to allow the VFD to connect to your PC via the serial port, which would be an added bonus.
Basically the software would have to poll one of the serial port's signal lines and when it detected that the PC was off, it would then go into "clock mode" and show the date and time, etc. You could take some of the C code used to control character LCDs and port it to pbasic to run on the stamp. Most of the code is just outputting the appropriate 1's and 0's to different pins on the VFD.
You could even get fancy and connect temperature sensors to the stamp and have it show the inside and outside temperatures along with the clock
I'm not sure what stamp model you would need, but be sure it has enough data lines to drive the VFD, and that it has an onboard serial port and RTC (Real-time-clock) for keeping the time. If you want to connect external sensors later on, make sure it also has some A/D channels on it.