En Windows Vista: C:\Users\<tu usuario>\AppData\<Local/Roaming (mira en los dos)>\Mozilla\Firefox\Profiles\<perfil>\bookmarks.html
En Windows XP: C:\Documents and Settings\<tu usuario>\Datos de programa\Mozilla\Firefox\Profiles\<perfil>\bookmarks.html
En GNU/Linux: ~/.mozilla/firefox/<perfil>/bookmarks.html
Simplemente debes copiar ese bookmarks.html al mismo directorio de tu nueva instalación. Si no copiaste ese archivo, me temo que has perdido los marcadores.