The exact wording is a person shall not store or gain access to information stored, in the terminal equipment of a subscriber or user unless the requirements ... are met.
In practical terms though, all they're storing is a key. The actual data is held elsewhere. In the same way, an entity tag on a cached object is like a key to identify whether the object has been modified on the server since the last time it was sent.
How would it be possible to spot that it was being used for tracking a user rather than just part of the normal functioning of the browser?
Even so, I think the answer is clear: it depends on whether you store data that permits you to infer privacy-intruding things about the user. If you store a cookie that just encodes preferences and you store no persistent data about the cookie on your side, you should be fine. It's the making a relationship between client local state and your customer profiles that's key.
If I recall correctly, some of these sites use cookies, Flash cookies and also unique Etags on an object in the browser cache to try to work around people blocking cookies from their domains.