As you have guessed any Probabilistic Encryption scheme (i.e. one which produces a randomized ciphertext output) requires that you transmit the seed for that randomness with the message. This value is called an Initialization Vector (IV) or a nonce and the combination of the Key and the IV/nonce is required to decrypt the message.
An picture of how this works for a block cipher in cipher block chaining (CBC) is depicted in the diagram:
The $\bigoplus$ symbol represents the XOR operation. From this diagram it should be fairly obvious that choosing a different random IV (and XORing it with the input) would result in very different ciphertext values.
Let's assume I am sending you a message and we have already shared a key. I would generate a random IV value and encrypt the message with that key/IV pair. I would transmit the IV and the ciphertext to you and then you would use the pre-shared key and the message-specific IV to decrypt the ciphertext.
The requirements on IV/nonce input vary depending on the encryption mode and cipher. In general IVs should be secure random values and nonces need only be unique (so a counter works as long as you don't repeat the same nonce for the same key).
Note that while the example above illustrates a block cipher, a probabilistic stream cipher will use similarly a IV/nonce along with a key. The IV would permute the initial state of the stream such that each encryption is unique.