For reference, the cookie law you refer to is officially known as Regulation 6 in the Privacy and Electronic Communications (EC Directive) Regulations 2003. Quotations in my answer are excerpts from public advice on this topic published by the UK data protection authority, The Information Commissioner's Office.
If a user has explicitly stated that they do not accept non-essential cookies, then any existing non-essential cookies placed by the website should be immediately removed, and this preference remembered so the cookies are not simply recreated a short while later.
While a user may not have explicitly accepted cookies when asked, it is possible that the website is operating on the basis of implicit consent - i.e. assuming you accept unless you take action to state otherwise. The idea of implicit consent being allowed is to help make the implementation of cookie questions/banners less disruptive to end users' website experiences.
"Consent does not necessarily have to be explicit ‘opt-in’ consent. Implied consent can also be valid. If you are relying on implied consent, you need to be confident that your users fully understand that their actions will result in cookies being set. However, in some circumstances (for example, collecting sensitive personal data such as health details) it is likely that explicit opt-in consent is more appropriate."
Ref: Guide to PECR: Cookies and Similar Technologies - What counts as Consent?
There are a few exemptions where consent for cookies is not required, and so a couple of examples for cookies that could be stored regardless of consent might include:
(a) a first-party cookie to remember the user's preference approving or disapproving the use of cookies (otherwise every time a new page is opened they would be asked the cookie question again);
(b) a first-party session cookie to remember who the user is after they have logged into the website; or upon interacting with an e-commerce website, to remember which products they have added to a cart.
These would be considered essential for the website to function. Non-essentially cookies, such as third-party tracking cookies would not be exempt.
"There is an exemption if:
(a) the cookie is for the sole purpose of carrying out the transmission of a communication over an electronic communications network; or
(b) the cookie is strictly necessary to provide an ‘information society service’ (eg a service over the internet) requested by the subscriber or user. Note that it must be essential to fulfil their request – cookies that are helpful or convenient but not essential, or that are only essential for your own purposes, will still require consent.
This means you are unlikely to need consent for:
(a) cookies used to remember the goods a user wishes to buy when they add goods to their online basket or proceed to the checkout on an internet shopping website;
(b) session cookies providing security that is essential to comply with data protection security requirements for an online service the user has requested – eg online banking services; or
(c) load-balancing cookies that ensure the content of your page loads quickly and effectively by distributing the workload across several computers.
However, it is still good practice to provide users with information about these cookies, even if you do not need consent."
Ref: Guide to PECR: Cookies and Similar Technologies - Are there any exemptions?
It is worth noting that guidance was not very specific/clear on how this legislation should be implemented, and so there are vast differences in websites approaches to this challenge. Also remember that some websites may actually be non-compliant with this legislation:
(a) through poor implementation - even if they ask the question if the website source code behind the scenes doesn't appropriately observe the end-user's preferences, or by appearing to be compliant while storing cookies which are not explained/justified in the privacy policy; or
(b) through conscious deliberate decision - deciding they did not want to comply with legislation they do not agree with on the basis that to implement a cookie question/banner might cost them customers by being unnecessarily disruptive to the user experience;
(c) through ignorance - there's always the possibility of a website owner being unaware this legislation exists if their webdesign company didn't tell them and they don't follow related news, or perhaps they have forgotten about it, etc.
