I ended up watching this video:
The problem here is that I have Adsense on my website, and google automatically adds cookies when it displays ads.
This is one of those tricky ones, not just from a legal standpoint but also from a technical standpoint. The legal issues are a bit beyond the scope of Webmasters SE and would really depend on legal advice obtained for your specific situation but mainly as I see it would be if technically you are bound by EU law if your site is not hosted in the EU and not specifically targeted to the EU.
From the technical standpoint due to browser security and cross domain issues there would be no way for you to do anything to affect the AdSense cookie (such as deleting it). I have used two different options in the past both of which where assessed by a clients legal rep's as being compliant...
In this impllementation we showed the cookie consent message at the top of the page and when the user clicked ok the AdSense code was added to the page and the ads where shown.
In this instance AdSense was required for the the site so the user was presented with a cookie consent page before being able to do anything in the site. Once the user agreed to the cookies, including the AdSense cookie the user was taken to the site, if they didn't agree to the cookies they where redirected to a different page saying that the site could not be used without cookies.
Either way you need to make an assessment on what solution meets your needs. Google has released a site which is at https://www.cookiechoices.org/ and provides information to site publishers on complying with EU cookie laws including third party solutions that can be used to enable cookie management for sites in line with EU requirements.