First I would set up the android sdk. Do a google search on that. If you already got that covered here are the programs I use daily.
Photoshop and fireworks - Image editing and creation software
7zip - archiving program which you will need to add apks and images into your update.zip
Draw9patch.bat - this is a program in the android sdk that let's you patch .9.png's
colorChangev3.jar - program that let's you change text colors within the theme.
xUltimate-d9pc - recompiles .9.png's after you've patched them.
xUltimate-opt - optimizes your png's and zipaligns apks
xUltimate2.1 - other random useful tools
Some sort of hex editor...I'm not sitting at my desk so I could tell you the name of it but I think its called HxD..
Smali and baksmali if you feel like torturing yourself and making manual edits to clock, date, clear button text and the color of the verizon wireless in the plldown as well as the titles for "ongoing, no notifications, etc"
I think that's pretty much all I ever use. I have other programs that I don't really use but I've called up from time to time. Everyone probably uses different tools, but this is what I use personally and it works for me.
I 'adb pull'ed my framework-res.apk and services.jar from my phone to ensure I was working off a compatible structure (Sapphire...great ROM). I then looked at other themes out there to see how they went about changing things and what icons were out there. This prevented me from reinventing the wheel, but care must be taken to give credit to the original theme creator.
Usage of GIMP inside of linux is what I use to edit the .pngs, but other use much more powerful pieces of software such as Photoshop.
This tool will unpack/decompile your framework-res.apk and restore the original .xmls as well as the images (some .9.pngs it has trouble with).
Editing the orignal .xmls will relieve you from the need to use a Hex Editor as you are able to go right into the proper .xml, such as the horizontal progress .xml to change colors in plain english.
You will need to use the tool to repack/compile your .apk, andyou won't be able to do a simple 'adb push' to get the repacked/compiled .apk to the phone. I tried this and it didn't go so well. I found that I had to make an update.zip and signing the .apk (which is more than you would have to do if you used the Hex edit methods). Reboot into recovery and apply the update.zip.
I know the tool can be used in Windows, but I haven't tried it yet, as I'm running Linux to do all my work.
Currently looking for tools that can uncompile my services.jar...I found a couple, but haven't worked with them yet.