We present ab initio investigations of the formation of magnetic moments in crystalline, quasicrystalline, and liquid Al-Mn alloys. We find that the appearance of local moments on the Mn sites is controlled by a local Stoner criterion. In the stable crystalline compound ${\mathrm{Al}}_{6}\mathrm{Mn}$ strong $\mathrm{Al}\ensuremath{-}p--\mathrm{Mn}\ensuremath{-}d$ hybridization enhances the formation of the structure-induced Hume-Rothery-like pseudogap at the Fermi level so that the compound is nonmagnetic. In supersaturated fcc solid solutions of the same composition this hybridization is strongly reduced; the local Mn density of states is impuritylike with a peak pinned at the Fermi level. This leads to a spin-glass-like magnetic structure with high moments on all Mn sites. Quasicrystalline and liquid alloys lie between these two extremes: In both icosahedral and decagonal quasicrystals $\mathrm{Al}\ensuremath{-}p--\mathrm{Mn}\ensuremath{-}d$ hybridization is generally strong in the ideal quasicrystalline structure, but there are certain local environments that support high magnetic moments on a small number of Mn sites. The local order is reduced, but does only gradually disappear in melting. This leads to an increase of the number of magnetic sites and explains the increase of magnetic susceptiblility on melting.