How to Create a Custom Theme

1. Go to your 12 hive
"C:\Program Files\Common Files\Microsoft Shared\web server extensions\12\TEMPLATE\THEMES"

2. Copy one of the theme folders, and rename it.
For example, copy SIMPLE and rename it to DSTheme

3. Inside the DSTheme folder, rename the .INF file to have the same name as your theme.
For example, DSTheme.INF

4. Open DSTheme.INF using a text editor, and rename all instances of "Simple" to "DSTheme"

5. Go to the SPTHEMES.xml file. It is located in
"C:\Program Files\Common Files\Microsoft Shared\web server extensions\12\TEMPLATE\LAYOUTS\1033\SPTHEMES.XML"

6. Add an entry in the <SPThemes> element:
<Templates>
  <TemplateID>DSTheme</TemplateID>
  <DisplayName>DSTheme</DisplayName>
  <Description>Some Description</Description>
  <Thumbnail>images/thdstheme.gif</Thumbnail>
  <Preview>images/thdstheme.gif</Preview>
</Templates>

In my case, I have put the thumbnail images in the 12 hive images folder:
"C:\Program Files\Common Files\Microsoft Shared\web server extensions\12\TEMPLATE\IMAGES"

This is what's going to show up when anyone previews the theme.

7. Do an iisrest for the server to recognize the new theme.

GOTCHA:
If you make any changes, you are going to have to:
a. do an iisreset again
b. change the theme to a different theme and apply
c. set the theme (again) to your custom theme, and apply

Not very pretty.