Why bother?
I wouldn't use this technique for sensitive data. It can be useful in combination with a regular session though - you can give the client a cookie with a normal session id, but also include all those key/value pairs that your application needs on every page. This way, you can avoid hitting your session storage for every page request.
You should aim to keep the amount of data pretty tight, since it will be sent with every request.
With that in mind, onwards...
Signing data with a hash
If the data isn't sensitive, you can sign the values with sha1 hash made from a combination of the key/value pairs and a shared secret. e.g.
$values=array(
'user_id'=>1,
'foo'=>'bar'
);
$secret='MySecretSalt';
$plain="";
foreach($values as $key=>$value)
{
$plain.=$key.'|'.$value.'|';
}
$plain.=$secret;
$hash=sha1($plain);
Now give the client a cookie with all the values and the hash. You can check the hash when the cookie is presented. If the hash you calculate from values presented by the client doesn't match the expected hash, you know the values have been tampered with.
Encrypting sensitive data
For sensitive data, you'll need to encrypt the values. Check out the mcrypt extension which offers a lot of cryptographic functions. For example, to use triple DES:
$key = "my key";
$plaintext = "userpassword";
$ciphertext = mcrypt_ecb (MCRYPT_3DES, $key, $plaintext, MCRYPT_ENCRYPT);
Now you can give the encrypted value to the client (after calculating your anti-tamper hash).
When it comes back, decrypt:
$plaintext = mcrypt_ecb (MCRYPT_3DES, $key, $ciphertext, MCRYPT_DECRYPT);
Cookie theft
With regards to cookie stealing, if you're putting user credentials into a cookie and trusting it, then someone who obtains that cookie can impersonate that user until the password is changed. A good practice is to remember how you authenticated a user, and only grant certain privileges if the user explicitly logged in. For example, for a forum you might let someone post, but not change their account details like email address.
There are other techniques for "autologin" cookies, involving giving such cookies a token value which you only allow to be used once. Here's a good article on that technique.
You could also look at including the client IP in a signed cookie, and if it doesn't match the IP presenting the cookie, you get them to log in again. This provides more protection, but won't work for people whose apparent IP address keeps changing. You could make it an optional feature, and give the user a way to opt out. Just an idle thought, I've not seen that done in practice :)
For a nice article which explains session theft, hijack and fixation see Sessions and Cookies which offers a few more techniques to try, such as using the User-Agent header as an additional signature.