The point here is the following result, that you can find in Zariski's book "Algebraic Surfaces", page 26. Zariski calls it "Extended Theorem of Bertini".
Theorem (Extended Bertini)
(1) The general curve of an irreducible linear system cannot have multiple points outside the base locus of the system.
(2) A reducible linear system, without fixed components, is necessarily composed with the curves of a pencil.
Here "reducible" [resp. "irreducible"] means that the general curve of the system is reducible [resp. irreducible].
Now, let us write $\mathcal{L}=Z+\mathcal{M}$, where $Z$ is the fixed part and $\mathcal{M}$ is the moving part. Then by Extended Bertini it follows that the general element $M \in \mathcal{M}$ is necessarily irreducible, unless $\mathcal{M}$ is composed with a pencil.
The last situation can occur. For instance let $S=\mathbb{P}^1 \times \mathbb{P}^1$, whose natural pencils are denoted by $|F_1|$ and $|F_2|$, and take $H=F_1+2F_2$ and $C \in |F_1|$. Then $H$ is very ample but $\mathcal{L}=|H-C|=|2F_2|$, which is without fixed part and composed with the pencil $|F_2|$. In fact, any element of $|2F_2|$ is the union of two curves in the pencil $|F_2|$, in particular it is not irreducible.
Remark. The situation described in J. C. Ottem's comment is slightly different. In that example, indeed, we have a fixed part $Z=2E$; the moving part, however, is irreducible.
