We develop a theory for graphene magnetotransport in the presence of carrier spin polarization as induced, for example, by the application of an in-plane magnetic field ($B$) parallel to the 2D graphene layer. We predict a negative magnetoresistance $sigma propto B^2$ for intrinsic graphene, but for extrinsic graphene we find a non-monotonic magnetoresistance which is positive at lower magnetic fields (below the full spin-polarization) and negative at very high fields (above the full spin-polarization). The conductivity of the minority spin band $(-)$ electrons does not vanish as the minority carrier density ($n_-$) goes to zero. The residual conductivity of $(-)$ electrons at $n_- = 0$ is unique to graphene. We discuss experimental implications of our theory.