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.