We explore, via analytical and numerical methods, the Kelvin-Helmholtz (KH) instability in relativistic magnetized plasmas, with applications to astrophysical jets. We solve the single-fluid relativistic magnetohydrodynamic (RMHD) equations in conservative form using a scheme which is fourth order in space and time. To recover the primitive RMHD variables, we use a highly accurate, rapidly convergent algorithm which improves upon such schemes as the Newton-Raphson method. Although the exact RMHD equations are marginally stable, numerical discretization renders them unstable. We include numerical viscosity to restore numerical stability. In relativistic flows, diffusion can lead to a mathematical anomaly associated with frame transformations. However, in our KH studies, we remain in the rest frame of the system, and therefore do not encounter this anomaly. We use a two-dimensional slab geometry with periodic boundary conditions in both directions. The initial unperturbed velocity peaks along the central axis and vanishes asymptotically at the transverse boundaries. Remaining unperturbed quantities are uniform, with a flow-aligned unperturbed magnetic field. The early evolution in the nonlinear regime corresponds to the formation of counter-rotating vortices, connected by filaments, which persist in the absence of a magnetic field. A magnetic field inhibits the vortices through a series of stages, namely, field amplification, vortex disruption, turbulent breakdown, and an approach to a flow-aligned equilibrium configuration. Similar stages have been discussed in MHD literature. We examine how and to what extent these stages manifest in RMHD for a set of representative field strengths. To characterize field strength, we define a relativistic extension of the Alfvénic Mach number M(A). We observe close complementarity between flow and magnetic field behavior. Weaker fields exhibit more vortex rotation, magnetic reconnection, jet broadening, and intermediate turbulence. Sufficiently strong fields (M(A)<6) completely suppress vortex formation. Maximum jet deceleration, and viscous dissipation, occur for intermediate vortex-disruptive fields, while electromagnetic energy is maximized for the strongest fields which allow vortex formation. Highly relativistic flows destabilize the system, supporting modes with near-maximum growth at smaller wavelengths than the shear width of the velocity. This helps to explain early numerical breakdown of highly relativistic simulations using numerical viscosity, a long-standing problem. While magnetic fields generally stabilize the system, we have identified many features of the complex and turbulent reorganization that occur for sufficiently weak fields in RMHD flows, and have described the transition from disruptive to stabilizing fields at M(A)≈6. Our results are qualitatively similar to observations of numerous jets, including M87, whose knots may exhibit vortex-like behavior. Furthermore, in both the linear and nonlinear analyses, we have successfully unified the HD, MHD, RHD, and RMHD regimes.