Make Categories and tags searchable in the default theme

I am wanting to make a directory that is based on cities and states. In order to do this I need an easy way for my visitors to search for specific companies/services by city and state.

The default theme has a search function that says " where it says what can we find for you today" and then an input box. This search function does not seem to search categories or tags. Is there a way to get this form to search categories and tags as well?

Thanks