I've been looking at this too, and I believe they fall under the category of pseudonymous data (most information taken from this helpful page):
Article 4(5)
‘pseudonymisation’ means the processing of personal data in such a manner that the personal data can no longer be attributed to a specific data subject without the use of additional information, provided that such additional information is kept separately and is subject to technical and organisational measures to ensure that the personal data are not attributed to an identified or identifiable natural person;
And regarding dealing with pseudonymous data:
Recital 26 (excerpt)
Personal data which have undergone pseudonymisation, which could be attributed to a natural person by the use of additional information should be considered to be information on an identifiable natural person. To determine whether a natural person is identifiable, account should be taken of all the means reasonably likely to be used, such as singling out, either by the controller or by another person to identify the natural person directly or indirectly.To ascertain whether means are reasonably likely to be used to identify the natural person, account should be taken of all objective factors, such as the costs of and the amount of time required for identification, taking into consideration the available technology at the time of the processing and technological developments.
My interpretation is this:
- A session cookie could conceivably be paired up with data stored by the web server to become identifiable (pseudonymous).
- Considering the means required, the time taken, and the low benefits to do so, we can deem it not reasonably likely, therefore a session ID is not identifiable.
More from Recital 26
The principles of data protection should therefore not apply to anonymous information, namely information which does not relate to an identified or identifiable natural person or to personal data rendered anonymous in
such a manner that the data subject is not or no longer identifiable. This Regulation does not therefore concern the processing of such anonymous information, including for statistical or research purposes.
They don't regulate you if the data subject is not or no longer identifiable.
Of course this would need to be evaluated on a cookie-by-cookie basis. The personal information at stake is vastly different between a web server session cookie, and a Google or Facebook tracking cookie, and hence reasonably likely changes.
References
Online PDF of full official regulation:
http://eur-lex.europa.eu/legal-content/EN/TXT/PDF/?uri=CELEX:32016R0679&qid=1490179745294&from=en
Online viewer for regulation:
https://gdpr-info.eu/
Page discussing anonymization and pseudonymization:
https://iapp.org/news/a/looking-to-comply-with-gdpr-heres-a-primer-on-anonymization-and-pseudonymization/
