The complex surface impedance of a number of GdBa2Cu3O7-delta single crystals has been measured at 10, 15, and 21 GHz using a cavity perturbation technique. At low temperatures a marked increase in the effective penetration depth and surface resistance is observed associated with a frequency dependent paramagnetic and antiferromagnetic alignment of the Gd spins. The effective penetration depth has a sharp change in slope at the Neel temperature, T(N)similar to2.2 K, with a peak in the surface resistance slightly above. The observed temperature and frequency dependence can he described by a model which assumes a negligibly small interaction between the Gd spins and the electrons in the superconducting state, with a frequency dependent magnetic susceptibility and a Gd spin relaxation time tau (s) being a strong function of temperature. Above T-N, tau (s), has a component varying as 1/(T-T-N), while below T-N it increases similar toT(-5).