We develop a theory for the electron-phonon interaction effects on the electronic properties of graphene. We analytically calculate the electron self-energy, spectral function, and the band velocity renormalization due to phonon-mediated electron-electron interaction, finding that phonon-mediated electron-electron coupling has a large effect on the graphene band structure renormalization. Our analytic theory successfully captures the essential features of the observed graphene electron spectra in the angle-resolved photoemission experiments, predicting a kink at approximately 200 meV below the Fermi level and a reduction of the band velocity by approximately 10-20% at the experimental doping level.