An analytical theory is presented for the damping of low-frequency adsorbate vibrations via resonant coupling to the substrate phonons. The system is treated classically, with the substrate modeled as a semi-infinite elastic continuum and the adsorbate overlayer modeled as an array of point masses connected to the surface by harmonic springs. The theory provides a simple expression for the relaxation rate in terms of fundamental parameters of the system: gamma=m omega(0)(2-)/A(c) rho c(T), where m is the adsorbate mass, <(omega)over bar>(0) is the measured frequency, A(c) is the overlayer unit-cell area, and rho and c(T) are the substrate mass density and transverse speed of sound, respectively. This expression is strongly coverage dependent, and predicts relaxation rates in excellent quantitative agreement with available experiments. For a half-monolayer of carbon monoxide on the copper (100) surface, the predicted damping rate of in-plane frustrated translations is 0.50X10(12) s(-1), as compared to the experimental value of (0.43+/-0.07)X10(12) s(-1). Furthermore it is shown that, for all coverages presently accessible to experiment, adsorbate motions exhibit collective effects which cannot be treated as stemming from isolated oscillators.