Diffuse interstellar bands (DIBs) trace warm neutral and weakly ionized diffuse interstellar medium (ISM). Here we present a dedicated, high signal-to-noise spectroscopic survey of two of the strongest DIBs, at 5780 and 5797{AA}, in optical spectra of 666 early-type stars in the Small and Large Magellanic Clouds, along with measurements of the atomic NaI D and CaII K lines. The resulting maps show for the first time the distribution of DIB carriers across large swathes of galaxies, as well as the foreground Milky Way ISM. We confirm the association of the 5797{AA} DIB with neutral gas, and the 5780{AA} DIB with more translucent gas, generally tracing the star-forming regions within the Magellanic Clouds. Likewise, the NaI D line traces the denser ISM whereas the CaII K line traces the more diffuse, warmer gas. The CaII K line has an additional component at ~200-220km/s seen towards both Magellanic Clouds; this may be associated with a pan-Magellanic halo. Both the atomic lines and DIBs show sub-pc-scale structure in the Galactic foreground absorption; the 5780 and 5797{AA} DIBs show very little correlation on these small scales, as do the CaII K and NaI D lines. This suggests that good correlations between the 5780 and 5797{AA} DIBs, or between CaII K and NaI D, arise from the superposition of multiple interstellar structures. Similarity in behaviour between DIBs and NaI in the Small Magellanic Cloud (SMC), Large Magellanic Cloud (LMC) and Milky Way suggests the abundance of DIB carriers scales in proportion to metallicity.