IANAL but as far as I can see, the rules are satisfied by adding something like "by using our website you agree that we can set cookies for the following purposes".
The problem with that is the fact that a cookie, Google Analytics for example, is set on page load so by the time they see that message they already have a cookie set.
One solution I'm thinking of using is to drop analytics for all sections of my site(s) except the interactive, script driven bits. I could change these so that on click signifies consent to set a cookie and that this would be a condition of entry.
The only way I can see for anyone to be certain of the correct interpretation of the law is for there to be a test case. Having gone to the High Court once before I wouldn't fancy being the one who took on that little task!