Currently /category and /tag 404 if you hit them directly. Is it possible to create a theme template to handle what would display on it? Mark Jaquith - http://twitter.com/#!/markjaquith/status/154324264047218688 - mentioned it might be possible to do with a custom rewrite rule, but I don't know where to begin to implement such a thing... Any help at all would be greatly appreciated.
This is absolutely possible. By default, the category archive page will be at domain.com/category/the_category. The file that is typically used for this rendering is
category.php, which is located in your theme directory.
To remove the /category/ part, so that your category archives are at domain.com/the_category, you can use the SEO Ultimate plugin. After installing the plugin, go to "Permalink Tweaker" and check the first box.
See more at the Codex: Category Templates page.
It possible to create your own template called category-archive or tag-archive
Wordpress uses archive template pages which are pretty much always included in any Wordpress theme.
Checkout your theme folder and then check the Wordpress Codex ( follow the link from Gavin above ) ... for examples of category or tag template pages. You can even have specific templates for different categories if you really want to be complex.
The plugins mentioned above will help for SEO but it sounds to me like you want your own template page.