Hey guys, I think you are making it out to be more complicated than it really is :). The OP is right that it's about POST/GET. The expiration notice is standard behaviour of browsers when you send a form using POST, leave the page and then go back. The reason is that browsers do not store POST data in history so they cannot property repeat the same POST request. However, data sent using GET are stored in history because GET data become part of the URL so such requests can be easily repeated by the browser when going back/forward. So the solution is to change the search form and the result page to use GET instead of POST and that's what google does.
Edit: to be more precise, browsers may cache POST data temporarily but even when they do they usually warn users that the data need to be re-submitted. This is because POST requests should be used when they actually cause some change in the system, for example you insert data to the database, delete a record, etc. Therefore, repeating the POST request without warning imposes a risk of undesirable action being performed for the second time. For requests that do not change anything in the target system, like search results (they only fetch data), GET should be used. Because GET requests don't (read: shouldn't) change the taget system state browsers can safely resend them without warning.
When you have done that you can go a step further and set the HTTP headers of the result page so that it is not re-downloaded on hitting the back button. You may get inspired by headers sent by google:
HTTP/1.1 200 OK
Cache-Control: private, max-age=0
Content-Type: text/html; charset=UTF-8
Date: Thu, 24 Jan 2013 14:11:47 GMT
Set-Cookie: PREF=ID=bdd9f4621316b989:U=ed51d8e7c619f888:FF=4:LD=pl:CR=2:TM=1331729163:LM=1359036707:GM=1:SG=1:S=W5y2DmtvP6dH3_Pq; expires=Sat, 24-Jan-2015 14:11:47 GMT; path=/; domain=.google.com
X-XSS-Protection: 1; mode=block
The important one is cache-control and also Expires. When cache-control is set to private and no no-cache directives are used then most browsers fetch the fresh page when you navigate to it via a link or form submission but will display it from cache when you press the back or forward button - this is what is usually desired for search result pages. In php you do it like this before sending output:
header("Cache-Control: private, max-age=0");