A very brief note (because I always forget at least one step!)
Copy a theme folder from C:\Program Files\Common Files\Microsoft Shared\Web Server Extensions\60\Template\Themes and rename it to the desired name for your new theme. Customise the theme accordingly – add your images and edit the various css files (theme.css is the most important).
Rename the .inf file in your current theme folder to the name of your new theme (same as folder name) and replace all instances of the old theme name with the new theme name in this folder.
Edit C:\Program Files\Common Files\Microsoft Shared\Web Server Extensions\60\Template\Layouts\1033\SPTHEMES.XML adding a node for the new theme. Eg:
<Description>Description of theme</Description>
Perform an iisreset.
Obviously you will need to apply the theme at http://server/your/current/web/_layouts/1033/themeweb.aspx. Note if the theme you have just edited and wish to apply is currently selected, you will need to apply another theme before reapplying this theme (as SharePoint caches themes with webs).
This article includes setting up of the thumbnail for when the theme is being applied http://www.graphicalwonder.com/?p=19 (as im feeling too lazy to explain it).
This is a good guide to the various css elements http://www.sharepointcustomization.com/resources/tipstricks/wss_cssguide.htm