I've come up with a solution now.
I'm using (not sure what it's called, but...) the part of the url after the # character.
So instead of visiting
http://www.domain.com/search/?crit=searchCriteria, the user visits
http://www.domain.com/search/#crit=searchCriteria.
Javascript can change document.location without the page reloading if only the part after the # has been changed. Then I use javascript to parse the "query string" after the # and do the relevant ajax.