In my sidebar I have two categories: 'Product' and 'News'. So I have created two category files category-product.php and category-news.php to display them in a different way.
My question is: how can I create permalinks to display these separate category pages? The default permalink always displays the category.php file. Can anybody please provide some ideas? I'm very new to WordPress.
WordPress selects template based on request parse results, not only on permalink structure.
When it determines that you request category page then it tries to find category-$slug.php file in theme folder. If this file is not found it tries to find category-$id.php and if it also absent, WP uses category.php.
So double check that product and news are categories slugs (not titles).
And try to use debug-bar plugin (http://wordpress.org/extend/plugins/debug-bar/). It can show request parameters.