This is a list of links to helpful resources on theming Drupal.

Drupal theme guide

The Drupal theme guide is the first place to start. Everything you need to get started is here, although sometimes the language and concepts are a little developer centric.
http://drupal.org/theme-guide

Accessibility Guidelines for Drupal themes

The Drupal theme layer is extremely powerful and you can incorporate many accessibility features via the sites theme—the flip side is that you can also make many mistakes. There is excellent information in the Drupal handbooks on accessibility and theming.
Tools, best practices and conventions: Accessibility
Designing Accessibility into Themes

Drupal 6 Theme Cheahsheet

This is a handy Drupal 6 PHPTemplate variables cheatsheet (PDF) available from minezone.org. Note that much of this information is included as comments in Drupals core template files and in Genesis also (with additional comments for Genesis specific variables).
Theming Cheatsheet PDF

Drupal Dojo

The Drupal Dojo has many great tutorials including videos and was one of the original non d.o tutorial sites.
http://drupaldojo.com/lessons/

Mustardseed Media

These guys have tonnes of fantastic videos covering all aspects of Drupal. Many are about or pertain to theming Drupal, in particular episode 24, how to convert a static theme to Drupal 6 (quick intro video).
http://mustardseedmedia.com/podcast

Lullabot

Tonnes of articles, podcasts, links, snippets and they have books and a video course - in short, go there now.
http://www.lullabot.com

Design for Drupal Group

Design for Drupal is about bringing the community of designers together to be a part of the drupal community. It's about enabling designers and themers to do great stuff, coordinate efforts, come up with crazy ideas, and build a movement to make drupal beautiful.
http://groups.drupal.org/design-drupal

Genesis and Zen starter theme Documentation

Both of these projects have excellent documentation and you can learn a lot from reading both sets of docs. Both themes also have extensive code commenting and include many useful snippets, methods and patterns themers can learn from or reuse.
Genesis Documentation
Zen Documentation

Front End Drupal: Designing, Theming, Scripting

Front End Drupal: Designing, Theming, Scripting, authored by Emma Jane Hogbin and Konstantin Käfer. This is a book to teach readers how to customize how Drupal looks, with a special focus on Drupal 6. Probably my pick for best book to get started with Drupal theming.
Amazon link
http://drupal.org/node/442298 (Drupal write up).

Packt Publishing

Packt Publishing have loads of great books on Drupal theming.
http://packtpub.com/

Acquia

Acquia offer a Drupal stack for easy installation of Drupal + the underlying AMP stack (Apache, MySQL and PHP) it runs on.
http://acquia.com/downloads

Theme Developer Module

The Drupal Developer module includes an extremely useful module called Theme Developer, which shows you stuff like template suggestions and theme functions.
http://drupal.org/project/devel

Coder Module

The Coder module assists with code review and version upgrade. It will tell where you need to clean up your code to Drupal coding standards.
http://drupal.org/project/coder

Content Templates (Contemplate)

This module is incredibly useful for finding the variables for theming various Drupal and CCK elements.
http://drupal.org/project/contemplate

Firebug

Firebug is a Firefox plugin that will make your theming life a lot easier. Use it to inspect HTML and CSS, and prototype styles live in the browser.
http://getfirebug.com

Web Developer Toolbar

Adds a menu and a toolbar to Firefox with various helpful web developer tools.
https://addons.mozilla.org/en-US/firefox/addon/60