Dan, I'm pretty sure what you're seeing is the results of Google's prefetch behavior:

<link rel="prefetch" href="http://www.berryhilltamales.com/"><a href="http://www.berryhilltamales.com/"><b>Berryhill</b> Baja Grill - We put the Ahhhh in Baja!</a>

Check this for more info:
http://www.google.com/help/features.html#prefetch

That link tells you how to disable prefetch in Firefox, which was the first thing I did when I learned about this, because I think prefetch is a scourge upon mankind.

Incidentally, Google ads can't set cookies on behalf of other sites, because cookies can be set only via HTTP headers, and only for the domain that request connects to. If the ads were frames/images which resulted in another background request, that'd be a different story.