Cookies aren't inherently evil or anything. They are a really important tool for a lot of situations. It's misuse that is the problem, persistent client-side storage is actually pretty critical for some stuff.
Anything that's not required to provide users with the service they're after must either not track them or ask for explicit consent before doing so.