Storing cookies isn't the trigger for the warning; no notification is required for cookies that are essential for the basic navigation and operation of the website.

So how would the browser differentiate those cookies from ones which are being used for data collection and tracking, which do require the warning message? It would require some sort of intent-signalling protocol between the website and the browser, which is probably more complicated than just requiring the site operator to include a bit of HTML.

For practical purposes, you could approximate it based on whether the cookie is first-party or third-party and on the amount of time until the cookie's expiration. For the most part, first-party cookies with a short time to expiration are allowed without warning under the EU law, all other cookies require the warning.