Update: My extra steps are not necessary if you put your 3rd party themes and modules under sites/all/. Makes updating a lot simpler.

Just updated Drupal to 6.13.
I'm really hating the process of updating. It should be simple and straight forward, but no. I have to piece together suggestions from several articles, user comments, etc.

Probably the best solution is the one on this page:
http://drupal.org/node/297496

At least it gives "ok" step by step instructions, but missed a few crucial things.

1. It seems to ignore that you probably have 3rd party modules.
2. It seems to ignore that you are probably using a different theme than the default.

So the solution seems to be to change step 3 to:

mv CHANGELOG.txt COPYRIGHT.txt cron.php includes index.php INSTALL.mysql.txt INSTALL.pgsql.txt install.php INSTALL.txt LICENSE.txt MAINTAINERS.txt misc profiles scripts update.php UPGRADE.txt xmlrpc.php d-backup

So you're effectively leaving the modules and themes folders there.

In step 7, when you move the new files into place, you'll need to merge the old module and theme files with the updated ones.

mv CHANGELOG.txt COPYRIGHT.txt cron.php includes index.php INSTALL.mysql.txt INSTALL.pgsql.txt install.php INSTALL.txt LICENSE.txt MAINTAINERS.txt misc profiles scripts update.php UPGRADE.txt xmlrpc.php ../
cp -rf modules themes ../


And viola! follow the rest of the steps and you should be back in business.
Also, to avoid any potential surprises, if there are module updates available, download and extract those straight into your modules and/or themes folder. That way modules that are incompatible with newer versions of Drupal don't get disabled.