84% of the matter in the universe is ``dark'', presently invisible to us except through its gravitational interactions. However, even tiny interactions between dark and visible matter could have striking effects on the primordial history of our universe: leaving traces of their existence in ionization and heating of the intergalactic gas, and in low-energy photons emitted during the cosmic dark ages and the epoch of reionization. Later, once galaxies formed, interactions amongst dark matter particles could lead to wide variation in the evolution of small satellite galaxies. I will discuss the interplay between current constraints, possible signals, and future probes, and describe new and improved tools to map out the possible signatures of dark matter interactions throughout the history of our cosmos.