Here is some PHP you can put in your template file. It only counts published posts, and hides future-dated posts, as well as private posts, but you can remove those lines if you do not want it to.
This code also assumes you are using a relatively new (2.3+) version of WordPress, which uses the more advanced category structure in the database.
In the script, (1, 2, 3) is the category IDs you want to count from. So if you wanted cats 12 and 34, replace it with (12, 34) etc..
The result will be in the $num_posts variable.
<?php
global $wpdb;
$table_prefix = $wpdb->prefix;
$mysqlnow = current_time('mysql');
$num_posts = (array)$wpdb->get_var("
SELECT COUNT(*)
FROM {$table_prefix}posts, {$table_prefix}term_relationships
WHERE {$table_prefix}posts.ID = {$table_prefix}term_relationships.object_id
AND {$table_prefix}term_relationships.term_taxonomy_id IN (1, 2, 3)
AND post_status = 'publish'
AND post_type = 'post'
AND post_password = ''
AND post_date < '$mysqlnow'
");
?>