Update: As many commenters have pointed out, this story does have a happy ending. CEO of Valve, Gabe Newell, ultimately came forward and explained away the possible spying, as in-fact a way to check for cheat DRM, which does exist apparently. The cheats, which were paid for, would often 'phone home' to make sure the user was legitimate. That's what Valve was checking for.
After decompiling the latest version of Valve's Valve Anti Cheat system (VAC), the guys at Counter-Strike: Global Offensive Reddit discovered that the latest version of the system reports Steam players' internet history to Valve.
More specifically, VAC now:
"Goes through all your DNS Cache entries (ipconfig /displaydns)
Hashes each one with MD5
Reports back to VAC Servers"
DNS Cache is the part of the operating system that stores the IP addresses of all recently accessed domains. It is not tied to a specific browser or program, making it an ideal place to find out all domains visited by the user.