Creating themes isn't really that complicated once you understand what exactly is going on. Here's the 2-cent tutorial:
First, create a directory for your theme, under wp-content/themes.
Second, create a style.css file. Inside this file, put the standard header. The most basic theme header is this one:
Theme Name: My Theme Name
Third, create an index.php. This will be the guts of the main page.
Now, as far as that goes, you can stop right there. Those two files are all you need for a theme. Ideally, however, you want to section it up a bit. There's lots of other theme templates you can create for specific parts of the site. The most common ones are header.php, footer.php, sidebar.php, comments.php, single.php, etc... In order to fully understand all these, you need to understand the Template Hierarchy.
When you request a webpage from a WordPress installation, it first decides what type of thing you're asking for. If you want the main page, a single post, a category archive, whatever... Based on that information, it looks for specific filenames in your current theme, in a specific order. When it finds one of them, then that's the one it calls and what generates your page. WordPress only calls one theme template (like single.php or index.php) per page request, so that template then can do things like get_header, get_footer, get_sidebar and so on to include other bits of the page. This allows you to build a logical separation between types of pages while keeping a similar look and feel throughout the whole site.
Remember, you're not writing HTML here. You're writing a bare page with PHP bits that will get filled in by content from inside the WordPress database.
Start with a style.css and an index.php. Examine the default theme's index.php for an example. Make a header and footer and sidebar. Add on single.php and other page-specific bits as needed. To add them on, copy the index.php to those filenames and then modify them to change those specific pages. It's easy, once you get used to it.