We examine wave propagation and the formation of shocks in strongly magnetized plasmas by applying a variational technique and the method of characteristics to the coupled magnetohydrodynamic (MHD) and quantum-electrodynamic (QED) equations of motion. In sufficiently strong magnetic fields such as those found near neutron stars, not only is the plasma extremely relativistic but the effects of QED must be included to understand processes in the magnetosphere. As Thompson & Blaes [1] find, the fundamental modes in the extreme relativistic limit of MHD coupled with QED are two oppositely directed Alfv\'{e}n modes and the fast mode. QED introduces nonlinear couplings which affect the propagation of the fast mode such that waves traveling in the fast mode evolve as vacuum electromagnetic ones do in the presence of an external magnetic field [2] (Heyl & Hernquist 1998). The propagation of a single Alfv\'{e}n mode is unaffected but QED does alter the coupling between the Alfv\'{e}n modes.