We propose a mechanism to control the interaction between adsorbates on graphene. The interaction between a pair of adsorbates---the change in adsorption energy of one adsorbate in the presence of another---is dominated by the interaction mediated by graphenes pi-electrons and has two distinct regimes. Ab initio density functional, numerical tight-binding, and analytical calculations are used to develop the theory. We demonstrate that the interaction can be tuned in a wide range by adjusting the adsorbate-graphene bonding or the chemical potential.