This is actually more complicated than I had originally thought, so I spent some time doing it myself and verifying the steps below. These are the exact steps I went through and was successful in creating a theme for my WSS site.

1. Open FrontPage 2003, Click on Format -> Theme -> then on the task pane that opens you can either modify an existing theme and save it, save it with a different name, or click “Create a new theme…” at the bottom of the task pane.
2. Then on the screen that opens you can modify the colors, text, fonts… and then click “Save As” and just save it in the default location and give it a one word name.
3. The theme will be saved in C:\Documents and Settings\<username>\Application Data\Microsoft\Themes\<theme name>
4. Then go to http://support.microsoft.com/default.aspx?scid=kb;en-us;295409&Product=fp2000 create the Unpack_elm.vbs script, place it in the folder from #3 and run it. Then delete the vbs file out of that folder once the files have been unpacked.
5. Copy the entire folder to C:\Program Files\Common Files\Microsoft Shared\web server extensions\60\template\themes
6. Open C:\Program Files\Common Files\Microsoft Shared\web server extensions\60\template\layouts\1033\spthemes.xml with NotePad.
7. Add a template by adding the lines below:

<Templates>

<TemplateID>halloween</TemplateID>  (this value should match the name of the folder you copied)

<DisplayName>Halloween</DisplayName> (this value can be anything, it will be displayed to the user)

<Description>Description</Description>    (again any value is fine, this value is unused by SharePoint)

<Thumbnail>../images/thice.png</Thumbnail> (this image won’t be used and so you can use this value or leave it blank)

<Preview>../images/thice.gif</Preview>  (This value is a .gif file of a screen shot of your theme applied to a site, it should be 300 x 179 and located here: C:\Program Files\Common Files\Microsoft Shared\web server extensions\60\TEMPLATE\IMAGES)

</Templates>
8. Perform an iisreset on the SharePoint server and now when you choose to Apply a Theme to a site your custom theme will be listed and you can apply it.