This is a great comment. However, in theory this has already been done through the
Data Protection Act
Unfortunately companies don't appear to get prosecuted for not complying at the moment and the rule isn't particularly enforcable. Not least because this is a UK law (although it might also fall into EU law) and the majority of sites you browse aren't UK based.
I should have stated it in the submission: Cookies can't collect personal data. If you enter personal data into a website and allow them to market to you because of it, then it is your own fault if they then market to you because of it. Another site can't collect that personal data without the site you entered it into giving them permission. If they do it illegally they should be punished, but this is nothing to do with the cookie. This should be what the EU focus on creating new laws. The cookies thing won't stop it.