This new legislation requires websites to obtain consent from visitors to store or retrieve any information on a computer or other web-connected device. This change is designed to protect online privacy by making consumers aware of how information is collected by websites (in the form of cookies) and enabling them to choose if they want this to happen.
So far there appears to be two options - the first is asking visitors to opt-in via a notice on your website. The second is to assume consent is given by using a clearly displayed cookies notice. This second option is the one that most sites that don't require a login seem to have.
Have a look at this example www.futureplc.com/cookies-policy/ and this image from a leading European bank which is clearly visible on their website (click to zoom).
Here are some example texts that websites are using for their new cookies policy:
Cookie notice examples
For more information about cookies check out www.allaboutcookies.org and www.aboutcookies.org