I have just recently completed by very own theme, and thought it would be a good idea to share what I've learned with everyone else.
I'm going to be writing a series of articles on my blog that will cover exactly how to create a theme, and what tags you'll need to know. The articles are being written with the assumption that you know HTML; you just don't know where to put it.
I posted the first of those articles last night. Last nights article was about how to get started. It covers the style.css, header.php, and footer.php files.
You can read the article right here: Designing a WordPress Template: The Basics
I hope you enjoy the articles.