We construct Hadamard states for the Yang-Mills equation linearized around a smooth, space-compact background solution. We assume the spacetime is globally hyperbolic and its Cauchy surface is compact or equal $R^d$. We first consider the case when the spacetime is ultra-static, but the background solution depends on time. By methods of pseudodifferential calculus we construct a parametrix for the associated vectorial Klein-Gordon equation. We then obtain Hadamard two-point functions in the gauge theory, acting on Cauchy data. A key role is played by classes of pseudodifferential operators that contain microlocal or spectral type low-energy cutoffs. The general problem is reduced to the ultra-static spacetime case using an extension of the deformation argument of Fulling, Narcowich and Wald. As an aside, we derive a correspondence between Hadamard states and parametrices for the Cauchy problem in ordinary quantum field theory.