How to display total number of posts found/fetched

I have the theme setup so that when a category is selected (by clicking on the default sidebar categories widget for example, or the archive page), the posts in that category get displayed 9 at a time… if there are more than 9, I get the pagination links.

I would like to know how to display the total number of posts in the category/archive/search, at the very top of the posts. For example: “Found 23 posts…”

I’ve tried echo ($wp_query->post_count), but this can only show a max number of 9.

Any suggestions?

Thanks.