$wp_query の中に、そのページで表示しようとしている投稿の情報がいろいろ入っているので、そこを覗けば簡単でした。
検索結果: <?php echo $wp_query->found_posts;?> 件
これだけです。
また、$wp_query->query_vars['paged'] には現在何ページ目かという情報が、$wp_query->query_vars['posts_per_page'] には 1ページあたりの表示件数が入っているので、そこから計算すれば「現在 1〜10 件目を表示中」みたいなのもすぐに出せます。
