Yes, you can create categories for each state, and then subcategories for each city in that state. Site users can then choose to search ads within a single city (i.e. sub-category).
One note about searching within categories:
I think the main search bar acts differently when searching site-wide versus searching in a specific category (e.g. searches through "tags" in the first case, but not the second). I'm still waiting for the Appthemes staff to help me understand how they programmed it to behave so I know what to tell my users. In the meantime, you can try that on their demo site (I use the search term, "clarity") if you want to see what I'm referring to.
