In the site  template file (webtemp*.xml), you specify the category using
the DisplayCategory in the <Configuration> attribute node. MSFT creates
the new categories  on demand as it's enumerates through all the
templates that need to be displayed in the site template picker.

I'm afraid I am referring to a different sort of site  Category. When
you create  a new site or subsite, you are allowed to pick a category
from Division or Region. Each of these categories  have sub-
categories. You can see them at:
http://<portal>/SiteDirectory/Pages/category.aspx

How do you add new categories here?

In the SiteDirectory site, you will see a list called Sites. This is
the list that is displaying sites on category.aspx. To change the
categories, you need to edit the Category column in the properties of
the sites list.

This replaces my previous reply which was done too quickly and was
not correct.

The categories  are columns in the Sites list. Edit the Sites list
properties, and remove or modify the columns "Division"
and "Region". Add other Choice columns that you want to include as
Categories. Then, edit the "Site Creation Categories" view on the
Sites list, and check the box next to those columns you want used as
categories.