We study RKKY interactions for magnetic impurities on graphene in situations where the electronic spectrum is in the form of Landau levels. Two such situations are considered: non-uniformly strained graphene, and graphene in a real magnetic field. RKKY interactions are enhanced by the lowest Landau level, which is shown to form electron states binding with the spin impurities and add a strong non-perturbative contribution to pairwise impurity spin interactions when their separation $R$ no more than the magnetic length. Beyond this interactions are found to fall off as $1/R^3$ due to perturbative effects of the negative energy Landau levels. Based on these results, we develop simple mean-field theories for both systems, taking into account the fact that typically the density of states in the lowest Landau level is much smaller than the density of spin impurities. For the strain field case, we find that the system is formally ferrimagnetic, but with very small net moment due to the relatively low density of impurities binding electrons. The transition temperature is nevertheless enhanced by them. For real fields, the system forms a canted antiferromagnet if the field is not so strong as to pin the impurity spins along the field. The possibility that the system in this latter case supports a Kosterlitz-Thouless transition is discussed.