From http://www.deluxeblogtips.com/2010/07/custom-post-type-with-categories-post.html

new_gist_file.php

add_action('init', 'demo_register_post_type'); function demo_register_post_type() {    register_post_type('demo', array(        'labels' => array(            'name' => 'Demos',            'singular_name' => 'Demo',            'add_new' => 'Add new demo',            'edit_item' => 'Edit demo',            'new_item' => 'New demo',            'view_item' => 'View demo',            'search_items' => 'Search demos',            'not_found' => 'No demos found',            'not_found_in_trash' => 'No demos found in Trash'        ),        'public' => true,        'supports' => array(            'title',            'excerpt'        ),        'taxonomies' => array('category', 'post_tag') // this is IMPORTANT    ));}