Most likely the themes are stored in your personal settings folder -- your Firefox profile folder. However, I'm not quite sure where and, actually, it may be more useful to have a list of them rather than a collection of files. Hopefully someone else will have specific suggestions.

Why are you losing your add-ons -- are you resetting Firefox, or is it resetting on its own? (One indication of a reset is an "Old Firefox Data" folder on your desktop.)

Also... Version 23 is not secure; Mozilla discloses security flaws after each new release. Is something holding you back from upgrading to Firefox 25? Please let us know so we can suggest solutions or workarounds.

Do you mean complete themes or Personas (lightweight themes) that only give the toolbar a background image?

• https://addons.mozilla.org/firefox/complete-themes/
• https://addons.mozilla.org/firefox/themes/

Installed complete themes are stored just like other extensions in the extensions folder in the Firefox profile folder.

If this is about Personas then only the images of the currently installed Persona are stored in the Firefox profile folder.
The background images of the other installed Personas are downloaded once you select them.

The list of installed Personas is stored as one of the user set prefs in the prefs.js file in the Firefox Profile Folder in the lightweightThemes.usedThemes pref in JSON object format ({"id":"#","name":"xxx",...}).

• http://kb.mozillazine.org/Profile_folder_-_Firefox

The first entry of that pref is the currently used Persona.

The images of the currently selected Persona are stored in the lightweighttheme-header and lightweighttheme-footer files in the Firefox profile folder.
So you would have to select all Personas one by one and make a backup copy of those two files.

• http://kb.mozillazine.org/Themes#Lightweight_theme

Check out FEBE from the Mozilla Add-ons Web Page.