The nature of dark matter is one of the most important outstanding problems in physics and cosmology. From observing astrophysical objects, we have learned that dark matter represents some 25% of the total energy of the universe, while ordinary matter weighs in at only about 4%. Although they make up a large fraction of the energy of the universe, dark matter particles interact with ordinary matter only very weakly, making their detection via interactions with ordinary matter difficult. We examine some of the constraints and cosmic clues for the nature of the dark matter, and consider its signatures in the sky in gamma rays and cosmic rays, underground in direct detection experiments, and at the Large Hadron Collider. These clues and constraints provide the basis for examining in greater detail a previously little explored class of models, where the dark matter carries a conserved global charge analogous to baryon number. We discuss a few explicit models, and examine their implications, including connections to astrophysical objects such as neutron stars.