You need to add a taxonomies argument to your registration array:

'taxonomies' => array('category') 

That is:

    array(
        'labels'    =>  array(
            'name'          =>  __( 'Products' ),
            'singular_name' =>  __( 'Product' ),
            'add_new_item'  =>  __('Add New Product'),
            'edit_item'     =>  __('Edit Product'),
            'search_items'  =>  __('Search Products')
        ),
        'public'        =>  true,
        'has_archive'   =>  true,
        'rewrite'       =>  array('slug' => 'products'),
        'taxonomies' => array('category')
    )

Reference:

http://codex.wordpress.org/Function_Reference/register_post_type