Usually Referrers are not passed along but instead by GET url-encoding containing the search keywords. Headers can be set and deleted, - are simple ASCI text, and are just part of the HTTP specification
http://www.w3.org/Protocols/rfc2616/rfc2616-sec4.html#sec4.2
message-header = field-name ":" [ field-value ]
field-name = token
field-value = *( field-content | LWS )
field-content = <the OCTETs making up the field-value
and consisting of either *TEXT or combinations
of token, separators, and quoted-string>
In PHP you can use the function header to set/overwrite and *header_delete* to remove headers, similar ones are available in separate packages in ruby and php.
As such when you write your own search engine, you can simply pass headers through. No major search engine will do so however, for a number of reasons, starting with legal arguments.