The ab initio Bethe-Salpeter equation (BSE) approach, an established method for the study of excitons in materials, is typically solved in a limit where only static screening from electrons is captured. Here, we generalize this framework to include dynamical screening from phonons at lowest order in the electron-phonon interaction. We apply this generalized BSE approach to a series of inorganic lead halide perovskites, CsPbX_{3}, with X=Cl, Br, and I. We find that inclusion of screening from phonons significantly reduces the computed exciton binding energies of these systems. By deriving a simple expression for phonon screening effects, we reveal general trends for their importance in semiconductors and insulators, based on a hydrogenic exciton model. We demonstrate that the magnitude of the phonon screening correction in isotropic materials can be reliably predicted using four material specific parameters: the reduced effective mass, static and optical dielectric constants, and frequency of the most strongly coupled longitudinal-optical phonon mode. This framework helps to elucidate the importance of phonon screening and its relation to excitonic properties in a broad class of semiconductors.