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].
Applying this to your situation, write $\mathcal{L}=Z+\mathcal{M}$, where $Z$ is the fixed part and $\mathcal{M}$ is the moving part. Then by the results above we see 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$ be a smooth quadric surface in $\mathbb{P}^3$ with rulings $|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 lines in the ruling $|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.