The self-diffusion of a particle on a flexible surface, such as a fluid bilayer membrane or a macroscopic interface, is analyzed theoretically in order to relate the macroscopic diffusion coefficient D-M, describing displacements in a laboratory-fixed plane, to the intrinsic surface diffusion coefficient D-s and to the configurational statistics of the surface. An exact result for D-M, is obtained for a rapidly fluctuating surface. For a static surface, rigorous bounds on DM are established and an effective medium approximation is derived that should remain accurate for strongly disordered surfaces. With the aid of these results, classical self-diffusion measurements can be used to study the configuration, bending rigidity, and interactions of flexible membranes and interfaces.