HTTP specification actually advises to use POST when sending data to a resource for computation.
Your search looks like a computation, not a resource itself. What you could do if you still want your search results to be a resource is create a token to identify that specific search result and redirect the user agent to that resource.
You could then delete search results tokens after some amount of time.
Example
POST /search
query=something&category=c1&category=c2&...
201 Created
Location: /search/01543164876
then
GET /search/01543164876
200 Ok
... your results here...
This way, browsers and proxies can still cache search results but you are submitting your query parameters using POST.
EDIT
For clarification, 01543164876
here represents a unique ID for the resource representing your search. Those 2 requests basically mean: create a new search object with these criteria, then retrieve the results associated with the created search object.
This ID can be a unique ID generated for each new request. This would mean that your server will leak “search” objects and you will have to clean them regularly with a caching strategy.
Or it can be a hash of all the search criteria actually representing the search asked by the user. This allows you to reuse IDs since recreating a search will return an existing ID that may (or may not) be already cached.