Dev Team
General
I've added the ability to recategorize published posts via the published post editing interface. This is somewhat clumsy, but since it had to be done anyway, this will allow recategorization until a dedicated recategorization (and bulk recategorization) interface can be made.
I've just uploaded the category support code. This is still definitely in BETA, and all of the functionality necessary to support categories isn't quite there yet (most notably, recategorization of posts), but there's enough here to be useful.
Tomorrow I'll post the steps necessary to take advantage of category support, but in the interim if you're using a straight-up powerblogs theme, just re-load it and you'll get the changes to the sidebar template. (If not, and you're impatient, read the documentation in the left and right sidebar editing pages; the new variables are documented.)
Also, FYI, you can create (and delete) categories from the site-wide tab.