Theme Views exposed filters, how to add count? For example in the case of filtering by taxonomy terms, I would like to add the node count next to each term in the exposed filter block. Already using Better Exposed Filters module as it allows to use checkboxes instead of select list.

Is there a way to do this? I can make a nice list of the terms with node counts using aggregation, but I can't think of an easy way to use ajax that way. :-)
What you are asking for is what is called faceted search.

If you want to have this feature you should think about using a search database that supports this, like Apache Solr. The problem is that it otherwise is going to be very heavy and complex to make, especially with views making the query for you. If you were to make this feature yourself with MySQL, it would probably be easier to code the entire page yourself, and add the facets for the terms in your custom form.

In Drupal 7 the search api module comes with support for Apache Solr and can do facets on both MySQL and Solr. It also have views integration.

For Drupal 6, you can use the Apache Solr Search integration module, which creates an API integration with Solr, making it easier to create facets with Solr. Use this would probably require that you custom made the entire form.