We present an analytic method to compute the one-loop magnetic correction to the gluon polarization tensor starting from the Landau-level representation of the quark propagator in the presence of an external magnetic field. We show that the general expression contains the vacuum contribution that can be isolated from the zero-field limit for finite gluon momentum. The general tensor structure for the gluon polarization also contains two spurious terms that do not satisfy the transversality properties. However, we also show that the coefficients of these structures vanish and thus do not contribute to the polarization tensor, as expected. In order to check the validity of the expressions we study the strong and weak field limits and show that in the former, the well-established result is reproduced. The findings can be used to study the conditions for gluons to equilibrate with the magnetic field produced during the early stages of a relativistic heavy-ion collision.