Nevertheless, there are other ways to capture such cookies. For instance one could use malware to capture search traffic, but the simplest solution remains to search SID cookies.
Using a malware to redirect the traffic of infected computers through a proxy controlled by the attack would allow to capture session cookies. Such infection has recently been detected by Google which displayed a banner on its search page . In that particular case, Google traffic redirection was merely a side effect which triggered the malware detection.
According to Google, a couple of millions of computers  were infected by this malware. Attackers could have captured a significant number of session cookies and run attacks described in our paper.
Googling for cookies
The simpler solution to find SID cookies is to search them. Typing the right query in Google provides a list of pages where people published captured HTTP traffic, including SID cookies (also works with Yahoo!).
If you replace your SID cookie by one of the cookies listed in these pages, you will receive the same personalized results than its owner. From these results you can quickly extract a list of visited results, Gmail contacts and Google+ acquaintances.
Not all these results contain full SID cookies and some of the listed SID cookies may have already expired, but this simple search should already provide many valid cookies to test the flaw. I've written a Chrome extension to simply replace the SID cookie for the "google.com" domain and quickly test different accounts. Once installed, click on the red button in the upper right corner, past the cookie value and click save.
On Firefox you could use the Web Developer extension to edit cookies (it does not seem to work on Firefox 5.0).
Linking data and PI
By publishing their (apparently innocuous) cookies users indirectly published part of their click-stream and associated it to their email address. Thus they established a public record of having visited these URLs , and this record is now linked to their name. From there, their full anonymized click-stream -- not reduced to visited search results -- could be de-anonymized by a tracking ad-network.
 Damian Menscher, "Using data to protect people from malware", http://googleonlinesecurity.blogspot.com/2011/07/using-data-to-protect-people-from.html
 Arvind Narayanan, "There is no such thing as anonymous online tracking", http://cyberlaw.stanford.edu/node/6701