There is a default archive.php template in all WordPress themes which has a static layout that looks like the blog and which is used any time a category archive is directly accessed using the category link or URL, that is where you have to put your code, in the place that you want.
So, basically you will have to do something like this wihtin the archive.php to get the number of post:
$category = get_category($id);
$count = $category->category_count;
Then you print it the way you want, echo "This category has ".$count." posts";, or something like that.