We investigate the effect of electron-phonon interactions on the coherence properties of single photons emitted from a semiconductor cavity QED (quantum electrodynamics) system, i.e., a quantum dot embedded in an optical cavity. The degree of indistinguishability, governing the quantum mechanical interference between two single photons, is calculated as a function of important parameters describing the cavity QED system and the phonon reservoir, e.g., cavity quality factor, light-matter coupling strength, temperature, and phonon lifetime. We show that non-Markovian effects play an important role in determining the coherence properties for typical parameter values and establish the conditions under which a Markovian approximation may be applied. The calculations are performed using a recently developed second-order perturbation theory, and the limits of validity are established by comparing to an exact diagonalization approach. We find that for large cavity decay rates the perturbation theory may break down.