It isn't. If you look at the EU's information about it [1], you must be able to refuse processing of information that's not necessary for the functioning of the site. Virtually no site outside the EU's own ones does that. Ironically, there are some that have them even though the only cookies they use are ones that are necessary for the functioning of the site, and so are exempt.

Note that this isn't just about cookies. It's pretty much any information being sent from the user's computer or stored on the user's computer: "Member States shall ensure that the use of electronic communications networks to store information or to gain access to information stored in the terminal equipment of a subscriber or user is only allowed on condition that the subscriber or user concerned is provided with clear and comprehensive information in accordance with Directive 95/46/EC, inter alia about the purposes of the processing, and is offered the right to refuse such processing by the data controller."

As far as I can tell, this is mostly because member states capitulated before online advertising exchanges (it's a directive, not a regulation, so it is implemented by member states) and allowed them to work around the clear intent of the directive.

[1] http://ec.europa.eu/ipg/basics/legal/cookies/index_en.htm