Howdy persyst,
The easiest way would be to give them a city or zip code, even if you choose to hide it from the front end. That search feature uses the Google Maps API, and so it has some limitations on what it is capable of. Check out the feature suggestion page where one of our devs commented on this. While your there, vote for the feature — it never hurts. Popular features are more likely to get implemented, period. Regardless of their difficulty.
You might also want to throw your vote behind this feature suggestion. It would allow you to filter down events based on the state that you input in your venue data. But, that is a drop down, not a search feature.
Does that all make sense and answer your question? Is there anything else? Cheers!
– Brook