We report on long-range interactions between adsorbates on metal surfaces with a surface state. A comparison of three adsorbate/substrate systems [Cu/Cu(111), Co/Cu(111), and Co/Ag(111)] suggests the general existence of such interactions and shows up common characteristics. In all cases, the interaction energy E(r) manifests itself up to a distance of 60 Angstrom, decays as 1/r(2), and oscillates with a period of lambda(F)/2. Our data are in excellent agreement with theory and establish the link between the spatial variation of the interaction energy and the adsorbate scattering properties. We demonstrate that the long-range interactions stabilize an ordered two-dimensional (2D) gas of adsorbates and thus create states of dilute 2D matter.