HTTP cookies violate the REST architectural style because they are independent of application state and they have no semantics, according to Roy Fielding’s doctoral dissertation Architectural Styles and the Design of Network-Based Software Architectures, § 6.3.4.2 ‘Cookies’:
An example of where an inappropriate extension has been made to the protocol to support features that contradict the desired properties of the generic interface is the introduction of site-wide state information in the form of HTTP cookies. Cookie interaction fails to match REST's model of application state, often resulting in confusion for the typical browser application.
Cookies also violate REST because they allow data to be passed without sufficiently identifying its semantics, thus becoming a concern for both security and privacy. The combination of cookies with the Referer [sic] header field makes it possible to track a user as they browse between sites.
So he suggests the following alternative:
As a result, cookie-based applications on the Web will never be reliable. The same functionality should have been accomplished via anonymous authentication and true client-side state. A state mechanism that involves preferences can be more efficiently implemented using judicious use of context-setting URI rather than cookies, where judicious means one URI per state rather than an unbounded number of URI due to the embedding of a user-id. Likewise, the use of cookies to identify a user-specific "shopping basket" within a server-side database could be more efficiently implemented by defining the semantics of shopping items within the hypermedia data formats, allowing the user agent to select and store those items within their own client-side shopping basket, complete with a URI to be used for check-out when the client is ready to purchase.
My understanding of his user preference example is the following. Let’s say that a website allows its users to choose between a light theme (the default) and a dark theme in a preference page at URI /preferences (like Stack Overflow). When a user chooses the dark theme, he should be redirected to the URI /preferences?theme=dark whose HTML representation will be the same as the HTML representation of the URI /preferences, except that it will be now in dark mode and the query ?theme=dark will be appended to all the embedded hyperlinks. That way, if the user selects for instance the embedded hyperlink to the home page at URI /home?theme=dark (not /home), then the HTML representation of the home page will also be in dark mode and the query ?theme=dark will also be appended to all its embedded hyperlinks. To revert to the light theme, then the user selects the embedded hyperlink to the preference page at URI /preferences?theme=dark, chooses the light theme in the preference page and should be redirected to the URI /preferences whose HTML representation will be the same as the HTML representation of the URI /preferences?theme=dark, except that it will be now in light mode and the query ?theme=dark will be removed from all the embedded hyperlinks. Is it what Roy Fielding meant?
Likewise for his shopping cart example, when the user adds a product i to cart, he should be redirected to a URI with a query ?product-{i}={product-i}&quantity-{i}={quantity-i} whose HTML representation will have that query appended to all its embedded hyperlinks. That way, when the user selects the check out hyperlink /checkout?product-1={product-1}&quantity-1={quantity-1}&…&product-n={product-n}&quantity-n={quantity-n}, the content of the shopping cart is sent to the website. Is it what Roy Fielding meant?
I believe you are correctly interpretting Fielding's thesis in the first case, but not the second.
Your interpretation of "preferences" seems exactly correct: it's perfectly reasonable to have multiple resources whose representations include the same information, but different presentation, like having a dark theme and a light theme as parallel resource structures.
But I believe that you misinterpret Fielding's proposal of "client-side shopping basket". He's not proposing introducing server side resources to be edited (after all, this capability already exists in the web we have today); but rather the introduction of a general purpose language for storing interesting pieces of client state on the client.
In other words, Fielding is talking about introducing within the HTML standard some controls (similar to the controls of a web form) that would allow the human to save some information would would later be loaded into a form when actually placing an order.
Imagine, if you will, a special kind of form that, when submitted, edits a resource that is local to the web browser itself. So you could pick items out of a catalog, and in doing so your local shopping cart resource would be modified. When you were ready to check out, the contents of your shopping cart would be available to sent to the server.
In the same way that forms are general purpose, and can be used for many different domains, so to we would want this shopping cart plumbing to be general purpose, so that it could be used for any sort of "copy this information to be used later" mechanism.
The trick (that didn't happen) is defining a standard and then getting everybody (browsers makers) to implement those standards in similar enough ways that everything just works.