We explore the interaction between two trapped ions mediated by a surrounding quantum degenerate Bose or Fermi gas. Using perturbation theory valid for weak atom-ion interaction, we show analytically that the interaction mediated by a Bose gas has a power-law behaviour for large distances whereas it has a Yukawa form for intermediate distances. For a Fermi gas, the mediated interaction is given by a power-law for large density and by a Ruderman-Kittel-Kasuya-Yosida form for low density. For strong atom-ion interactions, we use a diagrammatic theory to demonstrate that the mediated interaction can be a significant addition to the bare Coulomb interaction between the ions, when an atom-ion bound state is close to threshold. Finally, we show that the induced interaction leads to substantial and observable shifts in the ion phonon frequencies.