Memory effects probe the complexity of disordered matter and its fundamental constituents and interactions. While models based on independent elements capture generic memories, interactions are predicted to produce many interaction-induced memories which so far have been observed in artificial systems only. Here we reveal that archetypical disordered materials - polycrystalline alloys, crumpled sheets, and steel wool - store multiple memories that strengthen with repeated cycling - in stark contrast to predictions for non-interacting systems. Interacting-based models capture our observations and predict a cascade of interaction-induced memory motifs, including the dominant one observed here. Our results reveal hitherto hidden complexity in disordered media, opening a fresh route towards the observation, modeling and utilization of interaction-induced memories, including for in-materia computing.