The implementation of spectral stochastic Galerkin finite element approximation methods for Helmholtz equations with random inputs is considered. The corresponding linear systems have matrices represented as Kronecker products. The sparsity of such matrices is analysed and a mean-based preconditioner is constructed. Numerical examples show the efficiency of the mean-based preconditioners for stochastic Helmholtz problems, which are not too close to a resonant frequency.