As far as I understand it, the GDPR does everything and more than the cookie law was supposed to, so IMO it's about time we put that disaster behind us.
On the web, your approximate unique ID is your browser fingerprint. That can be used to join your activity to other activity. Your session cookie is your activity for your browsing session (or for users who never quit their browser, your entire computer uptime).
Think about it -- a cookie is information the web server gives to you; it's essentially a bookmark to your current position in the app. The server already knows where you were -- it saw you there!; it just doesn't know that you want to go back there on your next HTTP request.
Tracking data is data you give to the web server. Cookies are only one primitive to enable tracking. Cookies can be replicated by URL query parameters, subject to size constraints.
The biggest lie in most cookie warning popups is that you need to accept them for the site to function. It is often not true. Those are session cookies and you don't need to warn users about them, they're just allowed.
I didn't know this, and neither do any of the cookie warnings mention this. So like many people I thought the cookie law was the stupidest thing ever because like you say, you gotta have state. But the session cookies used to make a site hold state, those aren't considered tracking. When I learned about this little fact, it changed my opinion about the cookie law considerably.