In this paper we present a total variation diminishing (TVD) scheme for numerical relativistic magnetohydrodynamics (MHD). The eigenstructure of the equations of relativistic MHD has been cataloged here. We also describe a strategy for obtaining the physically relevant eigenvectors. These eigenvectors are then used to build an interpolation strategy that operates on the characteristic fields. The design of a linearized Riemann solver for relativistic MHD is also described. The resulting higher order Godunov scheme has been implemented in the author's RIEMANN code for astrophysical fluid dynamics. The resulting code is second-order accurate both in space and time. A number of design features have been used to make it a high-resolution scheme. It shows efficient and robust performance for several stringent test problems.