Encrypting the url parameters is the way to go:

Requests for:

http://duckduckgo.com/?q=hacker+news

Should HTTP redirect to something like:

http://duckduckgo.com/?enc=34g7h3giuh3g

Where 34g7h3giuh3g would be the ciphertext generated by encrypting "hacker news". That page knows what the search term was because it will have decrypted the parameters on the server side, but any referers would just contain "garbage", and it would also mean people can copy/paste the address bar about.

all the other person has to do then is perform a search to see the secret terms. granted, it's better than it showing up in plain text in the referrer, but you could easily write a script to scrape the actual terms...

What if you use the IP address of the user as a seed for the encryption? Then if someone else used the same key from a different IP they'd get different search terms?

That embeds the IP in the process and could theoretically be reverse-engineered.

Are there session ids? I assume that HMAC(secret + sessionID + ip + search terms) would be fine.

No sessions.

I see you do settings through a cookie or URL params. I'm out of ideas unless you hash the cookie + ip for a session ID fir that purpose.

Yes, you're right. I didn't think of that.