We report the first direct observation of the ultrafast electronic relaxation and coherent vibrational oscillation of strongly interacting gold nanoparticle aggregates measured by femtosecond laser spectroscopy. The electronic relaxation, reflected as a fast decay component with a time constant of 1.5-2.5 ps, becomes faster with decreasing pump power, similar to earlier observations of isolated gold nanoparticles. Surprisingly, periodic oscillations have been observed in the transient absorption/bleach signal and have been attributed to the coherent vibrational excitation of the gold nanoparticle aggregates. The oscillation period has been found to depend on the probe wavelength. As the probe wavelength is varied from 720 to 850 nm, the period changes from 37 to 55 ps. This suggests that the broad extended plasmon band (EPB) contains contributions from gold nanoparticle aggregates with different sizes and/or different fractal structures. Each of the different probe wavelengths therefore interrogates one subset of the aggregates with similar size or structure. Interestingly, the observed oscillation period for a given aggregate size determined by dynamic light scattering is longer than that predicted based on a elastic sphere model. One possible explanation is that the actual size of the aggregates is larger than what was observed from dynamic light scattering. An alternative, perhaps more likely, explanation is that the vibration of the aggregates is "softer" than that of hard spherical gold nanoparticles possibly because the longitudinal speed of sound is lower in the aggregates than in bulk gold. Persistent spectral hole burning was performed and yielded a hole in the nanoparticle aggregate's extended plasmon band, further supporting that the near-IR band is composed of absorption subbands from differently sized/structured aggregates.