You want your server to be able to decrypt the data, and nobody else. Therefore, your server must "know" something that other people do not, and that "something" is what cryptographers call a key.
However, there is no need for that key to be specific to the user. It can be a server-wide key. With symmetric encryption, the key to encrypt and the key to decrypt are the same; this will work for you if your server is also the system which does the encryption (since cookie values are set by the server, I suppose that this is your situation).
You want integrity too. In your system, the user is a potential attacker. The cookie is on his machine, so he could try to alter it. Encryption will prevent him from knowing the contents, but he may still make some "guesses" and alter it. Encryption does not ensure integrity by itself.
Combining encryption and integrity is not as easy as it seems. See this question for theory and pointers on the subject.
The server-wide key is sensitive information; manage it sensibly. In particular, you don't want to push it to all your backups (because lost/stolen backup tapes or disks are a classic leak mechanism), but you don't want to lose it either.