Based on this quick tip from WPRecipes, I was able to quickly figure out how to count and display the number of Custom Posts (of a particular type) that I had on a site.
$numposts = $wpdb->get_var("SELECT COUNT(*) FROM $wpdb->posts WHERE (post_status = ‘publish’ AND post_type = ‘listing’)");
if (0 < $numposts) $numposts = number_format($numposts);
post_type = 'listing' with whatever you’ve named your custom post type. Then, to get the number to display somewhere on your page, simply insert the following code where appropriate:
<?php echo $numposts ?>