Probabilistic encryption is a necessity for ANY public-key encryption scheme. The reason is that in such schemes anybody can perform the encryption, thus if the encryption was deterministic, that would allow to check a guess of the plaintext. That would be a total disaster in a lot of applications: enciphering a coin toss, a name on the class roll, a price, a bulletin vote, a credit card number or SSN, a password..
There's a tantalizingly simple but somewhat oversimplified explanation to:
If a probabilistic encryption algorithm is used, how does decryption return the correct message?
That explanation says that encryption takes the message, combines it with randomness, then enciphers; and decryption deciphers, then remove randomness to get the original message. That's exactly how it is done in RSA encryption with random padding, where combines sometime is as simple as appending randomness and fixed bits to the message (see e.g. RSAES-PKCS1-V1_5).
However, that simple explanation falls short of the goals of homomorphic encryption, because (as noted in the question) it does not yield a method to perform arithmetic on the encrypted message without holding the decryption key. That's why RSA encryption with random padding is not homomorphic, when RSA without padding is (multiplicatively, modulo the public modulus).
Secure homomorphic encryptions schemes do combine the message and the randomness as in the oversimplified explanation, but that combination is not by concatenation. For homomorphic randomized encryption to work, the combination of randomness and message must be by a method precisely matching the rest of the scheme.
The Paillier cryptosystem is one of the simplest example of randomness combination giving both security and homomorphicity.
As for a normal public-key encryption system, encryption requires the public key of the entity that will ultimately decipher. But (as the name implies) that public key is not secret. In Pailler, it is $(n,g)$ with large $n$ difficult to factor (similar to RSA) and choice of $g$ with $g^n\bmod n^2=1$ (typically $g=n+1$). Pailler encrypts message $m$ with $0\le m<n$ into $$E(m)=g^m\,r^n\bmod n^2\quad=c$$ where $r$ is a fresh random with $0<r<n$ and $\gcd(r,n)=1$.
Efficient decryption is possible knowing the factorization of $n$, with $D(E(m))=m$ for all valid $m$ and $r$.
That way of combining message $m$, randomness $r$, and public key $(n,g)$ is such that we have a homomorphic property:
$$\begin{array}{llll}
E(m_0)E(m_1)\bmod n^2&=g^{m_0}\,{r_0}^n&g^{m_1}\,{r_1}^n&\bmod n^2\\
&=g^{m_0+m_1}&{(r_0\,r_1)}^n&\bmod n^2\\
&=g^{(m_0+m_1\bmod n)+w\,n}&((r_0\,r_1\bmod n)+x\,n)^n&\bmod n^2\\
&=g^{m_0+m_1\bmod n}\,{(g^n)}^w&{(r_0\,r_1\bmod n)}^n&\bmod n^2\\
&=g^{m_0+m_1\bmod n}&{(r_0\,r_1\bmod n)}^n&\bmod n^2
\end{array}$$
$w$ and $x$ are integers bound to exist, that disappear later in the calculation. On the left side, that's by choice of $g$. On the right side, that's because the polynomial in $x$ raised to the power $n$ has all non-constant terms multiple of $n^2$.
We see that $E(m_0)E(m_1)\bmod n^2$ is identical to what the encryption of $m=m_0+m_1\bmod n$ could have been for choice of randomness $r=r_0\,r_1\bmod n$ .
Notice that the requirements $0\le m<n$ , $0<r<n$ and $\gcd(r,n)=1$ are met.
For a working decryption, we must thus have
$$D(E(m_0)\,E(m_1)\bmod n^2)=m_0+m_1\bmod n$$
or, for regular addition: if $0\le m_0<n/2$ and $0\le m_1<n/2$ then
$$D(E(m_0)\,E(m_1)\bmod n^2)=m_0+m_1$$
To produce a cryptogram per that homomorphic property, one needs
- at least one ciphertext $c_0=E(m_0)$ for an unknown message $m_0$, typically prepared by someone else (otherwise why use homomorphic encryption?)
- either
- A second similar $c_1=E(m_1)$, so as to be able to compute the ordinary product $c_0\, c_1=c$
- A new $m_1$ to combine, and the public key, which allows to compute $c_1$ and be back to the previous option.
- Typically at least, the public key (specifically, it's component $n$), to allows reduction of $c_1\,c_2$ modulo $n$, for two reasons
- concealing if a particular $c_i$ was involved in preparation of the ciphertext (otherwise determinable by testing if $c_i$ divides $c$)
- the reduced $c\bmod n^2$ is shorter than $c$ by a factor about 2.
