  Using the {\it ab initio} anisotropic Eliashberg theory including Coulomb
interactions, we investigate the electron-phonon interaction and the pairing
mechanism in the recently-reported superconducting Ca-intercalated bilayer
graphene. We find that C$_6$CaC$_6$ can support phonon-mediated
superconductivity with a critical temperature $T_{\rm c}=$6.8-8.1~K, in good
agreement with experimental data. Our calculations indicate that the low-energy
Ca$_{xy}$ vibrations are critical to the pairing, and that it should be
possible to resolve two distinct superconducting gaps on the electron and hole
Fermi surface pockets.
