A new approach is presented that allows a user agent to compute a compact browser cookie-like character string (called Geocookie) for a third party, whereby for any given geographic location the third party can either infer that the location is definitely not covered by the Geocookie, or it can infer that the location is probably covered by the Geocookie, depending on whether the user agent has or has not included the location beforehand. The approach extends the concept of a Bloom filter and combines it with Geohashes, thus making it possible to store information about visited geographic locations in the filter. Geocookies can be used in many different scenarios for location-based queries and location-based services, whenever a user agent wants to inform a third party about a set of visited locations such that the third party can compile a result that either favors or excludes these locations. In contrast to existing approaches such as session cookies that are mapped to server-sided stored location trajectories, Geocookies provide a compact and privacy-preserving structure which does not reveal the actual set of all visited locations, but provides a one-way check function which can be used by the third party to evaluate given locations against the Geocookie. In addition, Geocookies provide plausible deniability in case of location matches. This paper introduces a formal definition for Geocookies together with a discussion on practical applications and embedding into HTTP headers.