Ab initio calculations of surface-state mediated interactions between Cu adatoms on transition metal surfaces are presented. We concentrate on Co/Cu(111) and Co(0001) substrates and compare results with our calculations for Cu(111). Our studies show that surface states of Co/Cu(111) and Co(0001) are spin-polarized. We reveal that long range-interactions between adatoms are mainly determined by sp-majority states. In contract to Cu(111) and Co/Cu(111), the interaction between adatoms on Co(0001) is strongly suppressed at large adsorbate separations.