We measure the dependence of the conductivity of graphene as a function of magnetic field, temperature, and carrier density and discover a saturation of the dephasing length at low temperatures that we ascribe to spin memory effects. Values of the spin coherence length up to eight microns are found to scale with the mean free path. We consider different origins of this effect and suggest that it is controlled by resonant states that act as magneticlike defects. By varying the level of disorder, we demonstrate that the spin coherence length can be tuned over an order of magnitude.