This paper is concerned with the weak-moment magnetism in heavy-fermion materials and its relation to the non-Fermi-liquid physics observed near the transition to the Fermi liquid. We explore the hypothesis that the primary fluctuations responsible for the non-Fermi-liquid physics are those associated with the destruction of the large Fermi surface of the Fermi liquid. Magnetism is suggested to be a low-energy instability of the resulting small-Fermi-surface state. A concrete realization of this picture is provided by a fractionalized Fermi-liquid state which has a small Fermi surface of conduction electrons, but also has other exotic excitations with interactions described by a gauge theory in its deconfined phase. Of particular interest is a three-dimensional fractionalized Fermi liquid with a spinon Fermi surface and a U(1) gauge structure. A direct second-order transition from this state to the conventional Fermi liquid is possible and involves a jump in the electron Fermi-surface volume. The critical point displays non-Fermi-liquid behavior. A magnetic phase may develop from a spin-density-wave instability of the spinon Fermi surface. This exotic magnetic metal may have a weak ordered moment, although the local moments do not participate in the Fermi surface. Experimental signatures of this phase and implications for heavy-fermion systems are discussed.