How can encryption involve randomness?
There can be more than one ciphertext that maps back to the same plaintext. In mathematical terms, the encryption algorithm must be injective so that you can recover the plaintext for the ciphertext, but this does not prevent the ciphertext from encoding more information than the plaintext.

As a concrete example, consider modes of block cipher operation such as CBC, CTR or OFB. All these modes involve an IV (initialization vector) in addition to the plaintext, the block cipher algorithm and its key. (For CTR, the IV is called a nonce, but it plays a similar role.) The encryption function is deterministic for a given IV. The IV, on the other hand, may be chosen randomly (for CTR, it must be chosen randomly). Thus, unless the protocol specifies a deterministic method of choosing the IV (such as an agreed-upon constant), the IV is sent alongside the ciphertext. In fact, the output of the encryption software often consists of the IV followed by the cipher text stricto sensu. The IV itself is sent in plaintext; it does not (must not) contain any confidential information.

As another example, consider the PKCS1.5 mode (“padding scheme”) of RSA (defined in PKCS#1 version 1.5 — see p.22–25 of PKCS#1 v2.1). Simplifying a bit, this mode consists of concatenating a random string with the message, then applying the exponentiation operation. The ciphertext is $(P \mathbin\Vert M)^e \mod{n}$ where $\Vert$ is concatenation, $M$ is the message and $P$ is a padding string most of whose bits are random. To recover the message from the ciphertext $C$, apply the raw decryption operation $C^d \mod{n}$ and break up $C$ into padding (which is discarded) and message.