Magnetohydrodynamic (MHD) surface waves on liquid gallium are studied theoretically and experimentally in the small magnetic Reynolds number limit. A linear dispersion relation is derived when a horizontal magnetic field and a horizontal electric current is imposed. No wave damping is found in the shallow liquid limit while waves always damp in the deep liquid limit with a magnetic field parallel to the propagation direction. When the magnetic field is weak, waves are weaklyected, while in the opposite limit waves are strongly damped with shortened wavelengths. In a table-top experiment, planar MHD surface waves on liquid gallium are studied in detail in the regime of weak magnetic field and deep liquid. A non-invasive diagnostic accurately measures surface waves at multiple locations by reflecting the surface onto a screen, which is recorded by an Intensified-CCD camera. The measured dispersion relation is consistent with the linear theory with a reduced surface tension likely due to surface oxidation.