Just because you've logged out of a site doesn't necessarily mean the cookies have been deleted. Google can still track you just as effectively until you've cleared your cookies. In fact, if they store IP address and useragent information, they could continue tracking you even afterwards.
Now, I don't know that they do that, but they certainly have the technical means to do so.
> Even if you're logged out, one engineer told me, there are 57 signals that Google looks at -- everything from what kind of computer you're on to what kind of browser you're using to where you're located -- that it uses to personally tailor your query results.
He says they are signals used during ranking, not something to identify people.
Now, I don't know that they do that, but they certainly have the technical means to do so.