I finished hacking up Journalized-Blue to support the tags plugin. Since this is the only theme I have finished (wrt tags), I have made this the default theme for my blog.
Replacing categories with tags for this theme turned out to involve only two files, index.php and leftcolumn.php. Patches for both files are below. I made the theme “tags aware”, so if you have the tags plugin, the theme will show tags wherever it now shows categories. If you want both tags and categories, it’d be very simple to hack the patched files so that categories were always displayed.
The patches are .txt files. I can’t recall how to force these to display “as is” (my http-fu is weak, I’ll admit), but you can either right-click on these links and save the files locally or simply click on the links and then use your browser’s “view source” command to see the straight .txt files.