How do I create a cookie which is theft-proof and can not be tampered by a user/client?

Theft-proof means I can detect that this is coming from a different client IP or over a different route (like when client is behind proxy or something) .

Tamper proof means I can detect that the cookie is not valid and not sent by server.

A cookie must always be a Cryptographically secure pseudo random number (CSPRNG) that is also a Cryptographic Nonce or a value that is only used once. This value is used to access state information on the server side.

Why? It doesn't matter if the attacker modifies the value, he still cannot change the session state.

What about encrypting the cookie? In security it is best to avoid the problem all togather. This is a misuse of cryptography because it opens the door for attacks like the recent ASP.NET Oracle CBC Padding attack.

Some other features to add:

"Secure Cookies" - Terrible name but it is a flag that forces the cookie to always be transmitted over HTTPS. This insures that you never violate OWASP A9.

"HTTPOnly Cookies" - This makes it so that JavaScript cannot access document.cookie and makes cookies more difficult to hijack.

Make sure to patch your Session Riding aka CSRF.

Make sure to test your application for XSS by either using Sitewatch Free Edition or Wapiti. Even with HTTP Only cookies XSS can be used to bypass Token and Referer based CSRF protection.

I am not an expert in this field, but I felt I could contribute ideas to solve this problem.

1. Generate a large random(ish) number of fixed length.
2. Hash the number with a salt.
3. Append the salted hash to the end of the random number (from 1) and send it to the client.
4. Use SSL.
5. To check for integrity, split the fields out, add the salt to the first part, re-hash. If the hash does not match the second field, its been tampered with.

As I said before, I am not an expert, but this seems feasible.

To answer your question: You cannot detect if your cookie has been stolen or copied. After it leaves your server you have no idea what has happened to it - how could you?

However, you can detect if the original cookie data you sent has been tampered with using a Secure Hash Algorithm such as SHA-1.

The SHA-1 algorithm generates a hash signature that changes (or statistically is highly likely to change) if the data that it is applied to is changed. Because you generate the hash by using not only the data, but also a secret Salt, only you can generate the correct hash signature for a given piece of data. If someone modifies your data, they will be unable to make the corresponding change to the hash without the Salt value. You will of course check all data that is returned to verify that the hash signature that comes with it is correct. This requires you to append the hash signature to the end of the data, or some similar mechanism to keep the data and the hash signature together.

Bear in mind that the Salt value needs to be kept secret.

As @Rook has indicated, it is better from a security standpoint to avoid the problem altogether by not storing your data in a cookie at all. But we are not all writing internet banking applications, and a hash signature may be adequate for you needs.

It would be well worth your while to look at the resources available at OWSAP. OWASP has a series of Top 10 prioritised lists of the most common web application security vulnerabilities. Make sure you are familiar with these so you don't make that mistakes that thousands of others have made before.