We construct a simple and robust approach for deriving constraints on magnetic fields in galaxy clusters from rotation measure (RM) maps. Relaxing the commonly used assumptions of a correlation between the magnetic field strength and the plasma density and of a power-law (in wave number) magnetic field power spectrum, and using an efficient numerical analysis method, we test the consistency of a wide range of magnetic field models with RM maps of 11 extended sources in 5 clusters, for which the data were made available to us. We show that the data reveal no indication for a radial dependence of the average magnetic field strength, and in particular no indication for a correlation between the gas density and the field strength. The RM maps of a considerable fraction of the sources either require or are consistent with the presence of a spatially uniform magnetic field of a relatively small strength, 0.02-0.3 muG, which contributes significantly to the RM. The RM maps of all but one source do not require a power-law magnetic field power spectrum, and most are consistent with a power spectrum dominated by a single wave length. The uncertainties in the magnetic field strengths (and spatial correlation lengths) derived from RM maps exceed an order of magnitude (and often more). These uncertainties imply, in particular, that there is no indication in current RM data for a systematic difference between the magnetic field strengths in radio-halo clusters and in radio-quiet clusters. With the improvement expected in the near future of the quality and quantity of RM data, our analysis method will enable one to derive more accurate constraints on magnetic fields in galaxy clusters.