We develop a new theoretical model for the spectral formation process in accretion-powered X-ray pulsars based on a detailed treatment of the bulk and thermal Comptonization occurring in the accreting, shocked gas. A rigorous eigenfunction expansion method is employed to obtain the analytical solution for the Green's function describing the scattering of radiation injected into the column from a monochromatic source located at an arbitrary height above the stellar surface. The emergent spectrum is calculated by convolving the Green's function with source terms corresponding to bremsstrahlung, cyclotron, and blackbody emission. The energization of the photons in the shock, combined with cyclotron absorption, naturally produces an X-ray spectrum with a relatively flat continuum shape and a high-energy quasi-exponential cutoff. We demonstrate that the new theory successfully reproduces the phase-averaged spectra of the bright pulsars Her X-1, LMC X-4, and Cen X-3. In these luminous sources, it is shown that the emergent spectra are dominated by Comptonized bremsstrahlung emission.