soonyu,

I do restores all the time as a part of the regular work, to make test
copies of the database, etc. so my backups are tested frequently because of
that.  Of course, you should monitor the backup jobs daily to ensure that
they are running successfully.

I have heard it recommended (and think it is a good idea) to restore some
databases every week.  Rotate through your databases and servers from week
to week.

As far as documentation, a spreadsheet is fine to tick off the last test and
success or failure. (It only gets interesting when there is a failure, of
course.)  I use a workflow system to track problems and resolutions.

RLF