In my opinion, the web needs to be less reliant on cookies and state data, and websites should be adaptable to situations where they cannot store or access it. Websites can easily provide UI feedback for this issue. For instance, a store website unable to save a cookie can place a banner at the top saying something like "please enable cookies for this website in order to use the shopping cart." And then it's up to browser vendors to provide a simple, consistent, intuitive user interface for enabling cookies - such a UI should minimize the amount of instructional info a site's banner will need to contain in the first place.
The web really needs to be built around opting into site functionality on a site by site basis. It's been the opposite of this for a long time now and we've ended up where we are today... There are many reasons site operators will hate this, from legitimate concerns about usability or accessiblity, to business concerns about users not wanting to take the minimum amount of time to change a setting to add items to a cart resulting in reduced sales, or even malicious concerns about not being able to track users under a magnifying glass. As pissed off as these site owners will be, it's a change browser vendors can make without needing their permission the same way Apple added app-tracking-transparency controls much to the chagrin of companies like Facebook.
And yes, users will find one reason or another to complain about this, despite the fact that it will be optional. "It's like Vista's UAC prompts all over again!" "I shouldn't have to do extra work to add stuff to my cart!" etc. That's great that they don't care about being tracked and if they want to be the cattle of data mining companies that's fine. But there are plenty of people who, given the choice, will prefer the alternative, and over time sites will adapt. If sites purposefully punish people for not enabling cookies, and websites are interested in pissing off thier users, well there's always the option to close that site and use another... in any case I'd rather deal with that kind of fight then the situation we have now.