We present experimental results on the influence of magnetic fields and laser polarization on electromagnetically induced transparency (EIT) using Rydberg levels of $^{87}$Rb atoms. The measurements are performed in a room temperature vapor cell with two counter-propagating laser beams at 480nm and 780nm in a ladder-type energy level scheme. We measure the EIT spectrum of a range of $ns_{1/2}$ Rydberg states for $n=19-27$, where the hyperfine structure can still be resolved. Our measurements span the range of magnetic fields from the low field linear Zeeman regime to the high field Paschen-Back regimes. The observed spectra are very sensitive to small changes in magnetic fields and the polarization of the laser beams. We model our observations using optical Bloch equations that take into account the full multi-level structure of the atomic states involved and the decoupling of the electronic $J$ and nuclear $I$ angular momenta in the Breit-Rabi regime. The numerical model yields excellent agreement with the observations. In addition to EIT related experiments, our results are relevant for experiments involving coherent excitation to Rydberg levels in the presence of magnetic fields.