Hi @Grant Palin:
register_post_type() function is really agnostic to theme or plugin; you can use it in an
'init' hook in either place, it really depends on what you are trying to accomplish.
For example, if I'm setting up a custom site for a specific client I'll probably just register the post types in the theme. On the other hand, if I'm trying to create a reusable custom post type ("Event" might be an example) then I might register the Event post type in an Event-specific plugin.
However be aware that unless your post type is similar to a standard Post you'll likely still need specific theme support for it anyway. And with the pending release of Post Formats in v3.1, there really aren't many good reasons to define custom post types that are similar in use-case to a standard Post so you really have six of one, half dozen of the other.
Also, I frequently put custom post type registrations for a new site in an include file called by the theme's
functions.php file unless and until I get to the point of a fully generic feature in which case I'll move to a plugin (most of my clients have me writing reusable functionality that they then sell to their clients, and most of my work is related to custom post types. I rarely do work on code that will only run on a single website FWIW, JMMV.)
One thing I will say, I would avoid using plugins that provide a UI for creating custom post types and custom taxonomies like Custom Post Type UI and similar except for:
When you want to do some proof-of-concept prototyping or
When you want to empower an end-user that you don't want to give FTP access.
Why? Because these plugins all store their custom post type and taxonomy registrations in the database which makes it very difficult to version control them and also makes it much harder to launch a new version of the site from existing source code. Those UI plugins are really only best used when learning, tinkering, exploring, and/or doing a quick and dirty "what-if" / "proof-of-concept". (Of course the UI plugins are wonderful those those uses.)
What's more, the code to register a custom post type and a custom taxonomy is so easy to learn that there's really no reason for a WordPress professional to develop and deliver a system that doesn't hardcode its custom post types and custom taxonomies into PHP code, either in the theme or in a plugin, your choice. Matter of fact, I'm about to extract the CPT-UI plugin from a client project and replace with hardcoded PHP registrations this coming week.
Hope this helps. (If not, ask for more.)