Cookies are information stored on the end users device and require consent¹ per the ePrivacy directive, even if the cookies or similar technologies don't contain personal data. Conditions for consent are defined by the GDPR. This was also confirmed by the "Planet49" case.
1. consent is required unless the storage of or access to information on the end users device is either strictly necessary for a service explicitly requested by the user, or necessary for technical reasons. E.g. functional cookies like a shopping cart feature in a web shop are fine, as are cookies used solely for security purposes or technical features like TLS session resumption.
It is however likely that this cookie does qualify as personal data in the sense of the GDPR. The cookie contains an ID that lets you single out/distinguish this user from all other users, even though that ID doesn't link the user to a real-world identity. It is also possible to argue that the cookie is entirely anonymous, but the safer approach is to treat it as personal data. Similarly, other features of the website necessarily involve the processing of personal data, such as processing the user's IP address, if only for the purpose of responding to their HTTP requests.
The GDPR's criteria for valid consent are mainly about ensuring that the consent is a freely given unambiguous indication of the data subject's wishes. For example, consent can never be the default, it needs to be an opt-in. However, Art 7(1) GDPR says that the data controller has the burden of proof of showing that valid consent was given. The GDPR itself does not provide further guidance on what this means specifically. I would argue that it can be decomposed into two aspects:
Showing that valid consent was given. The manner in which you ask for consent must enable a free choice, and must respect that "no consent" is the default. For example, you could archive screenshots of the cookie management flow to show that there is a free choice. You could archive the frontend software so that it can be demonstrated that the cookie is not set until consent is given.
Showing that this user gave consent. There is a wide variety of opinions on how to do that.
My personal opinion is that the existence of a cookie paired with a valid consent flow to set that cookie demonstrates that the cookie can only have been set in a valid manner.
However, there are consent management solutions that provide additional insight, such as the user's entire history of giving and revoking consent. For example, the user's browser might generate a pseudonymous ID enabling that user's consent history to be stored on some server. Indeed, that would be personal data, and this would have to be disclosed transparently. It would not be valid to use the consent management information for other purposes, for example by using the consent management ID for analytics purposes.
Storing the user's consent history is definitely appropriate if you have a concept of identity, such as for signed-in users. I have doubts whether this is also helpful on websites that don't have user accounts, and I have not heard of a case where the existence of such records made a difference. After all, such records can only be relevant if the user gave consent but later disputes this in a complaint with a DPA or in a lawsuit.
Which approach to choose will depend on more specific guidance provided by your country's data protection authority, and on the risk balance appropriate for your business. After all, the purpose of such compliance work is not to be 100% safe from lawsuits, but to reduce risks from enforcement/litigation to acceptable levels. What is acceptable is ultimately a business decision. E.g. the only 100% safe way to do web analytics is to have no analytics at all, but that is not acceptable for most businesses.
