Adsorbate vibrational excitations are an important fingerprint of molecule/surface interactions, affecting temperature contributions to the free energy and impacting reaction rate and equilibrium constants. Furthermore, vibrational spectra aid in identifying species and adsorption sites present in experimental studies. Despite their importance, knowledge of how adsorbate frequencies scale across materials is lacking. Here, by combining previously reported experimental data and our own density-functional theory calculations, we reveal linear correlations between vibrational frequencies of adsorbates on transition metal surfaces. Through effective-medium theory, linear muffin-tin orbital theory, and the d-band model, we rationalize the squares of the frequencies to be fundamentally linear in their scaling across transition metal surfaces. We identify the adsorbate-binding energy as a descriptor for certain molecular vibrations and rigorously relate errors in frequencies to errors in adsorption energies. We also discuss the impact of scaling on surface thermochemistry and adsorbate coverage.