As angelwatt linked to, there's tons of tutorials. Google is your friend.
Also, it doesn't matter what tools you have; saying "I've got PS and CSSedit, I'm ready to make some WP themes!" is like saying "I bought a saw and a drill, so I'm ready to build a house!"
You need to understand how the Wordpress themes are put together, and then it really doesn't matter what you choose to work with. I can easily build WP themes from scratch now, but when I did my first one I found it very helpful to start with another theme's files and use them to help me understand how they were all supposed to fit together (don't use the default theme to do your learning -- there's a lot of goofy stuff in there that 99% of people don't put in other themes). Then, keep the Wordpress Codex close at hand for function reference and away you go.
You'll want a decent code editor when you're ready to give it a shot; I recommend TextMate if you're willing to spend some money, but Smultron is a great free alternative.