We investigate the RKKY interaction between magnetic impurities in both single layer and Bernal stacked bilayer graphene, finding a number of striking anomalies in the temperature dependence of this interaction. In undoped single layer graphene the strength of the RKKY interaction for substitutional impurities anomalously increases upon increasing temperature, an effect that persists up to and beyond room temperature. For impurities intercalated in the Bernal stacked bilayer and a doping that places the Fermi energy near the anti-bonding band edge, a qualitative change of the RKKY interaction with temperature occurs: a low temperature oscillatory interaction develops into a high temperature anti-ferromagnetic coupling, accompanied by an overall increase of the interaction strength. The origin of the temperature anomalies can be traced back to specific features of the density of states: the vanishing density of states at the apex of the Dirac cone in single layer graphene, and the 'kink' in the density of states at the anti-bonding band edge in the case of the Bernal bilayer.