We study the damping of the surface-plasmon resonance in gold nanoparticles that is caused by high-intensity optical excitation of the electron gas. Femtosecond pump-probe experiments are performed on gold nanoparticles embedded in dielectric matrices. Optical excitation of single-electron interband transitions leads to a pronounced broadening of the surface-plasmon line, which reflects the excitation-induced damping of the collective electron oscillation. The time evolution of the damping rate follows that of the electron temperature, showing that the damping rate is strongly influenced by transient variations in the electronic scattering rate. The dependence of the damping rate on the excitation energy shows evidence for fast relaxation of the optically generated d-band holes. In addition, cw transmission experiments performed with a scanning near-field optical microscope (SNOM) on single gold nanoparticles give access to the homogeneous line width of the surface plasmon.