If you are John Smith of 1313 Mockingbird Lane no cookie is needed partners just share info about targeting.
Sometimes it is more general Someone at your IP shopped for an Xbox one, so you get ads for Xbox One. We see this at my office a lot. I shop for something, and the guys in the office start to see ads for it.
Then there is the really scary ones. Your referrer data comes along with a search from Google or where ever, the ad network uses that with your metadata, or user data to know what you searched for, now they store all of those to track where you live based on you doing things like "Near:1313 Mocking bird lane" from Google Maps, and they now have your physical address, (or they get it from somewhere you bought something). Now your paper mail gets "Current Resident" targeted Spam.
Go a step further. Your friend Bob plays Candy Crush on Facebook, the game gets all the friends of Bob and their cities. Using the data from above we now know you are friends with Bob. So we start sending you spam that uses Bob's last name in it, or We just plain send you spam that uses Bob's Full name.
As someone who has managed large online ad campaigns you don't want to know how much information I can buy about you. The NSA is not nearly as Scary as Google with regards to how much they know about you. And Google will sell that stuff to anyone with a big enough budget, with no care as to how we want to use that data.