I accidentally deleted some builds for a job that I would have rather kept. I restored the builds on disk from backup, but they still do not show up when I am on the status page for that job.
I have tried both triggering another build for the job and re-starting Hudson.
How can I fully-restore these builds? Is there a DB that Hudson uses to store this type of information?
Depends what you restored. It sounds like you restored the workspace folder, but this folder is irrelevant for historical information. I would first shut down Hudson and than restore the build folder and the modules folder. Than you can restart Hudson. For more information ask the Hudson project.
Inside your %HUDSON_HOME% directory is a subdirectory called "jobs". Under "jobs" are subdirectories for every project. Inside each one are subdirectories for each build.
You need to make sure that jobs\<projectname> exists, and then copy the missing build directories inside.
Click "Manage Hudson/Reload Configuration From Disk" to make Hudson recognize the newly added builds. Not necessary to restart your servlet container (e.g. Tomcat) if you use one.