Cookies are for session management; the central problem with cookies is that people feel that servers will treat certain sessions as ephemeral, but instead those servers track these people for a long-term creepy analysis. One connected problem is that many sites require cookies in order to show public content. Public-content sessions should be entirely ephemeral, meaning that you shouldn't need a cookie in the first place. (The New York Times offends in this regard egregiously and persistently.)
You can easily comply with the EU law by either placing the notice on the login page or else not storing cookies. This means that anybody who abuses cookies in the above way needs to be loud about it; "we're not giving you an ephemeral presence like you think!" -- which actually not only fixes this problem but also creates an incentive to not abuse cookies in this way.
I am not saying that we should abandon sessions entirely, but that it would be nice if the 'default' session treatment followed the rules that online banking uses: when the browser is closed, all sessions are done. If we did this then we'd want to include a 'persistent login' mechanism, which would take the form of an in-browser 'would you like to sign in?' dialogue accompanying a web site. This means that unlike current HTTP authentication, it would have to be somewhat asynchronous; you are shown the ephemeral version of the page while the browser itself requests you to confirm that you want to join your long-term session there. (I was originally going to recommend that the browser just handle a digital signature scheme, but of course that does not solve the 'logging on to Facebook from your sister's computer' problem easily. Hm.)