Observational evidence from galactic to cosmological scales indicates that if Einstein-Newtonian gravity is the correct description of nature then the we are unable to account for the source of 80% of the matter in the universe. The nature of this unseen "dark matter" is different from that of ordinary matter, and provides clues to new forms of matter beyond the Standard Model of particle physics. A leading hypothesis is that Weakly Interacting Massive Particles were produced moments after the Big Bang, and today may be the massive relics that hold the Milky Way together. If so, it should be possible to detect them when they scatter from atomic nuclei in ultra-sensitive particle detectors operated deep underground. WIMPs have not yet been discovered, but searches to date have already begun to rule out some candidates which are also the quarry of the new Large Hadron Collider. A world-wide hunt over the next decade will hopefully discover dark matter -- and possibly resolve this decades-old mystery.