You didn't state what cache settings are producing this problem.
Joomla has several cache levels https://docs.joomla.org/Cache.
The most aggressive caching option is Page Caching (turned on via the cache system plugin). This will pick out a cached page based on the URI BEFORE your component is even run. Here I think your only option would be to set your form's method to "get", this will pass the form field's data as part of the querystring, so each unique search should generate a unique cached page. This also has the advantage of allowing users to press the browser's back button without the browser asking if they want to repost the form's data. However, the downside is that your page URL's might become less readable as the querystring can quickly become very long depending on the number of filters you have.
If you aren't using the system plugin, but are instead activating the cache via the site's global config then this is called 'view' caching, and can be handled by your component's controller.
In this case you will need to build a cacheid from the posted form data to ensure that a unique cached page is created per set of filters:
// Create the view
$view = $this->getView('myView', 'html');
// Build a cache id which will be unique per search:
$user = JFactory::getUser();
$uri = JURI::getInstance();
$input = JFactory::getApplication()->input;
$cacheId = serialize(array($uri, $input->post, $user->get('id')));
// Create the cache
$cache = JFactory::getCache('com_mycomponent', 'view');
$cache->get($view, 'display', $cacheId);
I've cut out and condenced the above code from Fabrik's list controller https://github.com/Fabrik/fabrik/blob/joomla3/components/com_fabrik/controllers/list.php which has to deal with a similar issue.
