Custom Post Types on Custom Categories

Let’s go. First, create your custom post type (products):

add_action( 'init', 'add_post_type_products' );
function add_post_type_products() {
    $labels = array(
        'menu_name'             => _x('Products', 'your_text_domain'), // the menu name text. This string is the name to give menu items. Defaults to value of name
        'name'                  => _x('Products', 'post type general name', 'your_text_domain'), // general name, usually plural. The same as, and overridden by $post_type_object->label
        'singular_name'         => _x('Products', 'post type singular name', 'your_text_domain'), // name for one object of this post type. Defaults to value of name
        'all_items'             => _x('All Products', 'your_text_domain'), // the all items text used in the menu. Default is the Name label
        'add_new'               => _x('Add Product', 'your_text_domain'), // the add new text. The default is Add New for both hierarchical and non-hierarchical types.
        'add_new_item'          => __('Add Product', 'your_text_domain'), // the add new item text. Default is Add New Post/Add New Page
        'edit_item'             => __('Edit Product', 'your_text_domain'), // the edit item text. Default is Edit Post/Edit Page
        'new_item'              => __('New Product', 'your_text_domain'), // the new item text. Default is New Post/New Page
        'view_item'             => __('View', 'your_text_domain'), // the view item text. Default is View Post/View Page
        'search_items'          => __('Search Product', 'your_text_domain'), // the search items text. Default is Search Posts/Search Pages
        'not_found'             => __('Not Found', 'your_text_domain'), // the not found text. Default is No posts found/No pages found
        'not_found_in_trash'    => __('Not found on trash', 'your_text_domain'), // the not found in trash text. Default is No posts found in Trash/No pages found in Trash
        'parent_item_colon'     => '', // the parent text. This string isn't used on non-hierarchical types. In hierarchical ones the default is Parent Page
        'slug'                  => 'products' // the slug for this post type
    );
    $args = array(
        'labels'                => $labels,
        'menu_position'         => 5, // The position in the menu order the post type should appear. show_in_menu must be true
        'menu_icon'             => theme_path . '/images/product-icon.png', // The url to the icon to be used for this menu
        'public'                => true, // Whether a post type is intended to be used publicly either via the admin interface or by front-end users
        'exclude_from_search'   => false, // Whether to exclude posts with this post type from front end search results
        'has_archive'           => true, // Support to archive-{post-type}.php file
        'publicly_queryable'    => true, // Whether queries can be performed on the front end as part of parse_request()
        'show_ui'               => true, // Whether to generate a default UI for managing this post type in the admin
        'show_in_menu'          => true, // Where to show the post type in the admin menu. show_ui must be true
        'show_in_admin_bar'     => true, // Whether to make this post type available in the WordPress admin bar
        'show_in_nav_menus'     => false, // Whether post_type is available for selection in navigation menus
        'hierarchical'          => false, // Whether the post type is hierarchical
        'rewrite'               => true, // Triggers the handling of rewrites for this post type
        'query_var'             => true, // Sets the query_var key for this post type
        'can_export'            => true, // Can this post_type be exported
        'supports'              => array('title','editor','author','thumbnail','excerpt','comments') // Supported values: title, editor, author, thumbnail, excerpt, trackbacks, custom-fields, comments, revisions, page-attributes, post-formats
    );
    register_post_type('products', $args);
    flush_rewrite_rules();
}

On line taxonomy you can enable or not the default tag and categories taxonomies. To create your custom taxonomy (category):

add_action('init', 'add_taxonomy_product_categories');
function add_taxonomy_product_categories() { 
    $post_types = array('products');
    $args = array( 
        'hierarchical' => true,
        'labels' => array( 
            'name'              => _x('Categories', 'taxonomy general name', 'your_text_domain'),
            'singular_name'     => _x('Category', 'taxonomy singular name', 'your_text_domain'),
            'search_items'      => __('Search Category', 'your_text_domain'), 
            'all_items'         => __('All Categories', 'your_text_domain'), 
            'parent_item'       => __('Parent Category', 'your_text_domain'), 
            'parent_item_colon' => __('Parent Category:', 'your_text_domain'), 
            'edit_item'         => __('Edit Category', 'your_text_domain'),
            'update_item'       => __('Update Category', 'your_text_domain'),
            'add_new_item'      => __('Add New Category', 'your_text_domain'),
            'new_item_name'     => __('New Category', 'your_text_domain'), 
            'menu_name'         => __('Categories', 'your_text_domain'), 
        ),
        'rewrite' => array( 
            'slug'              => 'product_categories',
            'with_front'        => false, // Don't display the category base before "/slug/" 
            'hierarchical'      => true // This will allow URL's like "/slug/sub-slug/" 
        )
    );
    register_taxonomy('product_categories', $post_types, $args);
    flush_rewrite_rules();
}

References on Codex:
Register Post Type
Register Taxonomy