What encryption algorithm is best for encrypting cookies?

No real reason not to go with AES with 256 bits. Make sure to use this in CBC mode, and PKCS#7 padding. As you said, fast and secure.

I have read (not tested) that Blowfish may be marginally faster... However Blowfish has a major drawback of long setup time, which would make it bad for your situation. Also, AES is more "proven".

This assumes that it really is necessary to symmetrically encrypt your cookie data. As others have noted, it really shouldnt be necessary, and there are only a few edge cases where there's no other choice but to do so. Commonly, it would better suit you to change the design, and go back to either random session identifiers, or if necessary one-way hashes (using SHA-256).
In your case, besides the "regular" random session identifier, your issue is the "remember me" feature - this should also be implemented as either:

a long random number, stored in the database and mapped to a user account;
or a keyed hash (e.g. HMAC) containing e.g. the username, timestamp, mebbe a salt, AND a secret server key. This can of course all be verified server-side...

Seems like we've gotten a little off topic of your original, specific question - and changed the basis of your question by changing the design....
So as long as we're doing that, I would also STRONGLY recommend AGAINST this feature of persistent "remember me", for several reasons, the biggest among them:

Makes it much more likely that someone may steal that user's remember key, allowing them to spoof the user's identity (and then probably change his password);
CSRF - Cross Site Request Forgery. Your feature will effectively allow an anonymous attacker to cause unknowing users to submit "authenticated" requests to your application, even without being actually logged in.

This is touching on two separate issues.

Firstly, session hijacking. This is where a third party discovers, say, an authenticated cookie and gains access to someone else's details.

Secondly, there is session data security. By this I mean that you store data in the cookie (such as the username). This is not a good idea. Any such data is fundamentally untrustworthy just like HTML form data is untrustworthy (irrespective of what Javascript validation and/or HTML length restrictions you use, if any) because a client is free to submit what they want.

You'll often find people (rightly) advocating sanitizing HTML form data but cookie data will be blindly accepted on face value. Big mistake. In fact, I never store any information in the cookie. I view it as a session key and that's all.

If you intend to store data in a cookie I strongly advise you to reconsider.

Encryption of this data does not make the information any more trustworth because symmetric encryption is susceptible to brute-force attack. Obviously AES-256 is better than, say, DES (heh) but 256-bits of security doesn't necessarily mean as much as you think it does.

For one thing, SALTs are typically generated according to an algorithm or are otherwise susceptible to attack.

For another, cookie data is a prime candidate for crib attacks. If it is known or suspected that a username is in the encrypted data will hey, there's your crib.

This brings us back to the first point: hijacking.

It should be pointed out that on shared-hosting environments in PHP (as one example) your session data is simply stored on the filesystem and is readable by anyone else on that same host although they don't necessarily know which site it is for. So never store plaintext passwords, credit card numbers, extensive personal details or anything that might otherwise be deemed as sensitive in session data in such environments without some form of encryption or, better yet, just storing a key in the session and storing the actual sensitive data in a database.

Note: the above is not unique to PHP.

But that's server side encryption.

Now you could argue that encrypting a session with some extra data will make it more secure from hijacking. A common example is the user's IP address. Problem is many people use the same PC/laptop at many different locations (eg Wifi hotspots, work, home). Also many environments will use a variety of IP addresses as the source address, particularly in corporate environments.

You might also use the user agent but that's guessable.

So really, as far as I can tell, there's no real reason to use cookie encryption at all. I never did think there was but in light of this question I went looking to be proven either right or wrong. I found a few threads about people suggesting ways to encrypt cookie data, transparently do it with Apache modules, and so on but these all seemed motivated by protecting data stored in a cookie (which imho you shouldn't do).

I've yet to see a security argument for encrypting a cookie that represents nothing more than a session key.

I will happily be proven wrong if someone can point out something to the contrary.

Security Warning: These two functions are not secure. They're using ECB mode and fail to authenticate the ciphertext. See this answer for a better way forward.

For those reading through wanting to use this method in PHP scripts. Here is a working example using 256bit Rijndael (not AES).

function encrypt($text, $salt) 
{ 
    return trim(base64_encode(mcrypt_encrypt(MCRYPT_RIJNDAEL_256, $salt, $text, MCRYPT_MODE_ECB, mcrypt_create_iv(mcrypt_get_iv_size(MCRYPT_RIJNDAEL_256, MCRYPT_MODE_ECB), MCRYPT_RAND)))); 
} 

function decrypt($text, $salt) 
{ 
    return trim(mcrypt_decrypt(MCRYPT_RIJNDAEL_256, $salt, base64_decode($text), MCRYPT_MODE_ECB, mcrypt_create_iv(mcrypt_get_iv_size(MCRYPT_RIJNDAEL_256, MCRYPT_MODE_ECB), MCRYPT_RAND))); 
}

Then to save the cookie

setcookie("PHPSESSION", encrypt('thecookiedata', 'longsecretsalt'));

and to read on the next page:

$data = decrypt($_COOKIE['PHPSESSION'], 'longsecretsalt');

Fast, Encrypted Cookies with Libsodium

If you need fast, secure encrypted cookies in PHP, check out how Halite implements them. Halite relies on the libsodium PECL extension to provide secure cryptography.

<?php
use \ParagonIE\Halite\Cookie;
use \ParagonIE\Halite\Symmetric\Key;
use \ParagonIE\Halite\Symmetric\SecretKey;

// You can also use Key::deriveFromPassword($password, $salt, Key::CRYPTO_SECRETBOX);
$encryption_key = new SecretKey($some_constant_32byte_string_here);

$cookie = new Cookie($encryption_key);

$cookie->store('index', $any_value);
$some_value = $cookie->fetch('other_index');

If you cannot install PECL extensions, ask your sysadmin or hosting provider to do it for you. If they refuse, you still have options.

Secure Encrypted Cookies in PHP, Hold the Salt Please

The other answers instruct you to encrypt your data with openssl or mcrypt, but they're missing a crucial step. If you want to safely encrypt data in PHP, you must authenticate your messages.

Using the OpenSSL extension, the process you would need to follow looks like this:

Preamble

(Before you even think about encryption) Generate a 128-bit, 192-bit, or 256-bit random string. This will be your master key.

Do not use a human-readable password. If you, for some reason, must use a human-readable password, ask Cryptography SE for guidance.

If you need special attention, my employer offers technology consulting services, including development of cryptography features.

Encryption

Generate a random Initialization Vector (IV) or nonce. e.g. random_bytes(openssl_cipher_iv_length('aes-256-cbc'))
Use HKDF or a similar algorithm for splitting your master key into two keys:
1. An encryption key ($eKey)
2. An authentication key ($aKey)
Encrypt your string with openssl_encrypt() with your IV and an appropriate modate (e.g. aes-256-ctr) using your encryption key ($eKey) from step 2.
Compute an authentication tag of your ciphertext from step 3, using a keyed hash function such as HMAC-SHA256. e.g. hash_hmac('sha256', $iv.$ciphertext, $aKey). It's very important to authenticate after encryption, and to encapsulate the IV/nonce as well.
Package the authentication tag, IV or nonce, and ciphertext together and optionally encode it with bin2hex() or base64_encode(). (Warning: This approach might leak cache-timing information.)

Decryption

Split your key, as per step 2 in encryption. We need the same two keys during decryption!
(Optionally, decode and) unpack the MAC, IV, and ciphertext from the packed message.
Verify the authentication tag by recalculating the HMAC of the IV/nonce and ciphertext with the user-provided HMAC by using hash_equals().
If and only if step 3 passes, decrypt the ciphertext using $eKey.

If you want to see how this all looks together, see this answer which has sample code.

If this sounds like too much work, use defuse/php-encryption or zend-crypt and call it a day.

Remember Me Cookies

However, we have a requirement to implement a 'remeber me' feature. The accepted way to go about this is by setting a cookie. If the client presents this cookie, he or she is allowed access the system with (almost) equal rights as if he/she presented the valid username password combination.

Encryption is actually not the correct tool for this job. You want to follow this process for secure remember me cookies in PHP:

Generating a Remember Me Token

Generate two random strings:
1. A selector which will be used for database lookups. (The purpose of a random selector instead of just a sequential ID is to not leak how many active users are on your website. If you're comfortable leaking this information, feel free to just use a sequential ID.)
2. A validator which will be used to authenticate the user automatically.
Calculate a hash of validator (a simple SHA-256 hash will suffice).
Store the selector and the hash of the validator in a database table reserved for automatic logins.
Store the selector and validator in a cookie on the client.

Redeeming a Remember Me Token

Split the incoming cookie into the selector and validator.
Perform a database lookup (use prepared statements!) based on selector.
If a row is found, calculate a hash of the validator.
Compare the hash calculated in step 3 with the hash stored in the database, once again using hash_equals().
If step 4 returns true, log the user in to the appropriate account.

This is the strategy that Gatekeeper adopted for long-term user authentication and it is the most secure strategy proposed to date for satisfying this requirement.