This is a great security question regarding the server side cookies. One must understand the mechanics of what they work with to ensure they are building secure software. Security There is no added significant security risk when a server has access to cookie information. Servers are already a privileged system that needs to be strongly protected.
[Comment] ...how can [a] server identify a new request is from the same user as some previous requests, without memory of the previous requests coming from some user...?
If the server stores encrypted or signed data in a client-side cookie, the server can verify that. It can deduce that only an authorised server could have stored that cookie.
A good modern example of this is JWT - https://jwt.io/. They can be sent in a cookie, but typically they go into the authorization header for a Web API HTTP Request. If you understand JWT more, you can understand the cryptographic principles that can be deployed with simpler mechanisms for smaller amounts of data in cookies.
Knowledge
how could a server match a cookie just received from a client to some session or other information created in the past?
Cookies are stored in the client's browser with a timeout after which they are deleted. Upon every HTTP request to the server, they are sent to the server automatically. The cookie is usually set by the server, not the client (but it's possible).
The server typically uses the direct value, or decrypts a value for a local database lookup. For example, the UserID value could be stored in the cookie encrypted.
A key architectural reason for using cookies, is to maintain a session linked to the identity of the user. They are also used as a type of distributed data store, so the server has this information already upon HTTP Request without having to look it up on disk/db which incurs latency.
A session might be associated with a key (GUID) in memory on the web server, or it could be a key for a new session record in a database. In both cases, the key is relayed by cookie.
How does a server store cookie information?
The server MAY store them, but that's not how people view them conceptually. In a way the server does store the data - a session key is the primary key of a record (database or hashed dictionary lookup). For an encrypted UserID, the server-side does have they key too. In a way, the client isn't "storing" it, it's more like a copy of a key. But it is possible, and likely occurs, that clients store distinct information that isn't persisted on the server-side.
is it true that a server always has records of cookie info?
No. Here are some scenarios where the server doesn't have records of the cookie info:
Javascript on the client-side sets a cookie. Eg. "OrganisationID=10" indicating that the user has changed organisation context across all browser tabs.
Server encrypts some data for the user to hold onto. Eg. "Roles=Admin,Developer,Staff" so that the server can enforce roles on functions without needing to do a lookup on the database
Although the server-side doesn't always have that information somewhere it usually does, because cookies are used for context. When there is a HTTP Request, the server needs to know who it's coming from, what roles they are authorized to use, and whether they have been seen before.
