I am not expert, but in most cases you need permission from data protection agency. I think it is pretty similar to LG TV uploading list of files on local disks.
Yeah, for my company I have to comply with some serious regulations over what I can do with customer data, what I can collect, etc... I can't imagine that ripping a customers entire web history is anywhere near compliant.
When I think about how much work I do on home machines with Steam installed, I can't even begin to imagine how much of a security breach this could be at larger companies.
If they're sending hashes of the data rather than the data itself, they could quite easily argue that it's not "personally identifiable information" (remember that data protection only covers certain things).
On the other hand, if they want to know if you have visited a certain site, they can just hash the domain name and compare it to the hashes that were sent over, so the privacy is just illusory.
If it's in the EULA? I didn't check, though it crossed my mind, fixing a tap [faucet] instead.
http://pastebin.com/PTG57bXb is the .deb and the online "Steam Agreement" - section 2A of the later is probably most relevant from a brief look through (unless they've hidden things under non-relevant headings). That requires you to give them rights to run "the software".
There are parts about their rights to your UGC, but that doesn't seem pertinent really.
Nothing seems to be a warranty from you as user to Valve giving them rights to snoop around your system and upload data they find.