Propagation and scattering of lasers present new phenomena and applications when the plasma medium becomes strongly magnetized. With mega-Gauss magnetic fields, scattering of optical lasers already becomes manifestly anisotropic. Special angles exist where coherent laser scattering is either enhanced or suppressed, as we demonstrate using a cold-fluid model. Consequently, by aiming laser beams at special angles, one may be able to optimize laser-plasma coupling in magnetized implosion experiments. In addition, magnetized scattering can be exploited to improve the performance of plasma-based laser pulse amplifiers. Using the magnetic field as an extra control variable, it is possible to produce optical pulses of higher intensity, as well as compress UV and soft x-ray pulses beyond the reach of other methods. In even stronger giga-Gauss magnetic fields, laser-plasma interaction enters a relativistic-quantum regime. Using quantum electrodynamics, we compute a modified wave dispersion relation, which enables correct interpretation of Faraday rotation measurements of strong magnetic fields.