If an encryption algorithm is meant to convert a string to another string which can then be decrypted back to the original, how could this process involve any randomness?
Surely it has to be deterministic, otherwise how could the decryption function know what factors were involved in creating the encrypted string?
Well, the idea behind randomized encryption is that a single plaintext $P$ can encrypt into many different ciphertexts $C_1, C_2, ..., C_n$, and that when we encrypt, we pick one of those ciphertexts randomly. Of course, because the decryptor has no way to knowing apriori which one we picked, it must be able to map any of those ciphertexts back into the original plaintext.
If the ciphertext $C_i$ was exactly as long as the plaintext $P$, then there would be an obvious problem; if the plaintext was $k$ bits long (and hence there are $2^k$ distinct plaintexts), and there are $n$ ciphertexts for each plaintext, we have $n2^k$ ciphertexts (which must all be distinct), and only $2^k$ bit patterns available to express them.
The obvious solution to this is that the ciphertexts must be longer than the corresponding plaintext. In particular, if each ciphertext was at least $\log n$ bits longer, then everything fits nicely; we have $n2^k = 2^{k + \log n}$ ciphertexts and $2^{k + \log n}$ bit patterns to express them.
Now, the obvious question is: why does anyone bother? The answer to that is, well, it provides better protection than deterministic methods. It is generally the case that we'll send multiple messages with the same key. If we happen to send the same message twice, deterministic encryption would make that obvious to the attacker (because the ciphertexts will be exactly identical), and that is information we'd rather the attacker not have. Even if we'll never send the same message twice, we may send related messages. While it is possible to design a deterministic encryption method that doesn't leak any information when given related messages, it's harder than you'd think. In contrast, the goal behind nondetermanstic encryption is to make all the messages look perfectly random (even if we decide the send the same message multiple times); that turns out to be a rather easier goal to achieve.
One common way nondetermanistic encryption is implemented with CBC mode; the encryptor chooses a random block (known as an IV; 128 bits if he is using AES), and uses that to encrypt the message. He sends the IV along with the encrypted message to the decryptor, who can uniquely decrypt the message. One nice property about CBC mode is that it is easy to prove that if the IV is chosen randomly, and that the underlying block cipher is secure, then an attacker cannot distinguish the encryption from a random source.
Say you have an algorithm whose security properties are not very good if a lot of fairly predictable data is encrypted with the same key. You can fix this by adding randomness to the process.
You encrypt like this:
You generate a random key.
You encrypt the data with that random key.
You encrypt the random key with the shared key.
You send the encrypted data from step 2 along with the encrypted key from step 3.
You decrypt like this:
You decrypt the encrypted random key with the shared key.
You decrypt the encrypted data with the random key that you just decrypted.
The shared key that is re-used is only used to encrypt random data. The possibly predictable input is only encrypted with a random key that is never reused. Now, even an attacker who gets to choose what data you encrypt has no control over what data is encrypted with the persistent key.
Also, this means that an attacker cannot tell if two encrypted outputs correspond to the same plaintext just by comparing them. If an attacker can get the system to encrypt either the plaintext he suspects and he intercepts the ciphertext, he can tell what the original message encrypted by simple comparison. Adding randomness defeats this attack too.
For example, an attacker could intercept a daily encrypted message that was always "nothing to report". An attacker could just wait for the day the ciphertext is different from the previous day and infer that the plaintext has changed and therefore that something was happening. You can defeat this by including something like a serial number or something in the plaintext, but this creates the complexity of having to figure out what's adequate to accomplish that task, requiring the people who compose the plaintext to thoroughly understand the properties of the encryption algorithm.
If it's a block cipher, if you do "nothing to report - 10:43PM January 7", will the first few bytes of the encrypted message match if the next message is "nothing to report - 10:43PM January 8" (This is a good reason never to encrypt anything but random data with a key you plan to reuse.)
This is just a simple example, but it shows two things. First, it shows how an encryption process can be perfectly reversible but still involve randomness. Second, it shows how using randomness in an encryption process can improve the security properties.
