We report the results of a search for pair production of doubly-charged Higgs bosons via ppbar to H^{++}H^{--}X to mu^+mu^+mu^-mu^-X at sqrt{s} = 1.96 TeV. We use a dataset corresponding to an integrated luminosity of 1.1 fb^{-1} collected from 2002 to 2006 by the D0 detector at the Fermilab Tevatron Collider. In the absence of an excess above the standard model background, lower mass limits of M(H^{pmpm}_L) > 150 GeV/c^2 and M(H^{pmpm}_R) > 127 GeV/c^2 at 95% C.L. are set, respectively, for left-handed and right-handed doubly-charged Higgs bosons assuming a 100% branching ratio into muons.