I'm not sure how you lost them all, but my best guess is that you may have accidently logged in your computer with a different name.
To recover them try this (for internet explorer)
1 - right click on "my computer" and hit "explore".
2 - then left click on "my computer"
3 - then left click on "Local Disk C:"
4 - left click on "documents and settings"
5 - find your user name and left click on it
6 - Then click on favorites to see if they are still there.
If not, go back to step 5 and try a different user name that you might have logged in under.
As last resort click on "administrator" "default user" and "all users" to see if they are under any of them.
Chances are, they are all around there somewhere still.
Might sound like a lot of little steps, but just takes a minute and saves a lot of pain trying to find bookmarks again.
good luck!
Verax