The icy mantles of interstellar dust grains are the birthplaces of the primordial prebiotic molecular inventory that may eventually seed nascent solar systems and the planets and planetesimals that form therein. Here, we present a study of two of the most abundant species in these ices after water: carbon dioxide (CO2) and methanol (CH3OH), using TeraHertz (THz) time-domain spectroscopy and mid-infrared spectroscopy. We study pure and mixed-ices of these species, and demonstrate the power of the THz region of the spectrum to elucidate the long-range structure (i.e. crystalline versus amorphous) of the ice, the degree of segregation of these species within the ice, and the thermal history of the species within the ice. Finally, we comment on the utility of the THz transitions arising from these ices for use in astronomical observations of interstellar ices.