If you are a WordPress newbie and you are willing to learn it, the 1st step would be to find a really good guide of how to create a WordPress theme from scratch. Small Potato from WPDesigner gives a really detailed tutorial for beginners. Best this about those is that he gives a free PDF download of all 3 book parts.
First part is called How to Design a WordPress Theme where you will find a PDF file containing design instructions, a folder of images (step-by-step screenshots), and a PSD file for you to mess around with.
Second part is How to Slice a WordPress Theme which will help you to deal with layers and CSS.
Last, but not the least, third part is How to Code a WordPress Theme. This part handles PHP programming part.
There is another resource that we received the link for recently (May 2009) from WebHostingSearch. The title is Stop Tweaking! Create Your Own WordPress Theme. I hope you will enjoy it.
Note from 12-feb-2014: Although this post is obsolete today and the links do not longer work, this post has historical value for Inchoo. It was the very first blog post on this site.