Ultrafast laser-induced magnetization dynamics in ferromagnetic thin films were measured using a femtosecond Ti:sapphire laser in a pump-probe magneto-optic Kerr effect setup. The effect of plasmon resonance on the transient magnetization was investigated by drop-coating the ferromagnetic films with dimensionally-tuned gold nanorods supporting longitudinal surface plasmon resonance near the central wavelength of the pump laser. With ~4% nanorod areal coverage, we observe a >50% increase in demagnetization signal in nanorod-coated samples at pump fluences on the order of 0.1 mJ/cm(2) due to surface plasmon-mediated localized electric-field enhancement, an effect which becomes more significant at higher laser fluences. We were able to qualitatively reproduce the experimental observations using finite-difference time-domain simulations and mean-field theory. This dramatic enhancement of ultrafast laser-induced demagnetization points to possible applications of nanorod-coated thin films in heat-assisted magnetic recording.