When the search is performed, you'll want to call setcookie() at the top of the script, using whatever unique characteristic of the search seems most appropriate.
However, in order to ensure that matching searches are not stored as cookies, you'll want to also check for the existence of the same data in (another, as it were) previous cookie "call".
Since cookies are now available to PHP via the $_COOKIE superglobal array, it ought to be fairly easy to simply put the setcookie call in a conditional, and check the superglobal first with [man]in_array/man and the unique datum for this particular search.
HTH,
