When showing list of content (i.e. Posts, Custom Post Type) on Category Page, the main $WP_Query renders posts of default Posts type. To show content from different post type we've to alter the main $WP_Query.
There are few different ways using which we can alter the $WP_Query. But here is one of the way to alter $WP_Query without removing existing conditions in Query.
// Define global variable.
// Define arguments to alter query.
$args = array(
'post_status' => 'publish',
'post_type' => 'CUSTOM_POST_TYPE',
// Add extra conditions to existing query.
The above code uses query_posts() function, to alter existing $WP_Query. To alter the existing Query, I've merged $WP_Query->query_vars and new filter conditions and then pass that to query_posts function.
NOTE: Add your custom post type name instead of CUSTOM_POST_TYPE, in post_type.
I've found this way very easy to understand and this also works fine with default pagination.