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 Å, in optical spectra of 666 early-type stars in the Small and Large Magellanic Clouds, along with measurements of the atomic Na I D and Ca II 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 Å DIB with neutral gas, and the 5780 Å DIB with more translucent gas, generally tracing the star-forming regions within the Magellanic Clouds. Likewise, the Na I D line traces the denser ISM whereas the Ca II K line traces the more diffuse, warmer gas. The Ca II K line has an additional component at ˜200-220 km s-1 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 Å DIBs show very little correlation on these small scales, as do the Ca II K and Na I D lines. This suggests that good correlations between the 5780 and 5797 Å DIBs, or between Ca II K and Na I D, arise from the superposition of multiple interstellar structures. Similarity in behaviour between DIBs and Na I in the Small Magellanic Cloud (SMC), Large Magellanic Cloud (LMC) and Milky Way suggests the abundance of DIB carriers scales in proportion to metallicity.