Picasa stores its database in C:\Users\\AppData\Local\Google
The database is in the Picasa2 and Picasa2Albums folders. To restore the database on a fresh install of Picasa, just copy the database over and replace the empty one.
It was useful that Windows 8 kept the previous Windows files in a Windows.old folder as I had forgotten to backup the Picasa database separately. That has since been rectified by adding a new operation to SyncToy.