We propose a scheme for implementing the CNOT gate over qubits encoded in a pair of electron spins in a double quantum dot. The scheme is based on exchange and spin-orbit interactions and on local gradients in Zeeman fields. We find that the optimal device geometry for this implementation involves effective magnetic fields that are parallel to the symmetry axis of the spin-orbit interaction. We show that the switching times for the CNOT gate can be as fast as a few nanoseconds for realistic parameter values in GaAs semiconductors. Guided by recent advances in surface codes, we also consider the perpendicular geometry. In this case, leakage errors due to spin-orbit interaction occur but can be suppressed in strong magnetic fields.