Accurate phase-space coordinates (three components of position and velocity) of individual stars are rapidly becoming available with current and future resolved star surveys. These data will enable the computation of the full three-dimensional orbits of tens of thousands of stars in the Milky Way's stellar halo. We demonstrate that the analysis of stellar halo orbits in frequency space can be used to construct a 'frequency map' which provides a highly compact, yet intuitively informative way to represent the six-dimensional halo phase-space distribution function. This representation readily reveals the most important major orbit families in the halo, and the relative abundances of the different orbit families, which in turn reflect the shape and orientation of the dark matter halo relative to the disc. We demonstrate the value of frequency space orbit analysis by applying the method to halo orbits in a series of controlled simulations of disc galaxies. We show that the disc influences the shape of the inner halo making it nearly oblate, but the outer halo remains largely unaffected. Since the shape of the halo varies with radius, the frequency map provides a more versatile way to identify major and minor orbit families than traditional orbit classification schemes. Although the shape of the halo varies with radius, frequency maps of local samples of halo orbits confined to the inner halo contain most of the information about the global shape of the halo and its major orbit families. Frequency maps show that adiabatic growth of a disc traps halo orbits in numerous resonant orbit families (i.e. having commensurable frequencies). The locations and strengths of these resonant families are determined by both the global shape of the halo and its stellar distribution function. If a good estimate of the Galactic potential in the inner halo (within ˜ 50 kpc) is available, the appearance of strong, stable resonances in frequency maps of halo orbits will allow us to determine the degree of resonant trapping induced by the disc potential. We show that if the Galactic potential is not known exactly, a measure of the diffusion rate of a large sample of ˜ 104 halo orbits can help distinguish between the true potential and an incorrect potential. The orbital spectral analysis methods described in this paper provide a strong complementarity to existing methods for constraining the potential of the Milky Way halo and its stellar distribution function.