Recent years have seen increased theoretical and experimental effort towards the first-ever detection of cosmic-ray antideuterons, in particular as an indirect signature of dark matter annihilation or decay. In contrast to indirect dark matter searches using positrons, antiprotons, or gamma-rays, which suffer from relatively high and uncertain astrophysical backgrounds, searches with antideuterons benefit from very suppressed conventional backgrounds, offering a potential breakthrough in unexplored phase space for dark matter. This article is based on the first dedicated cosmic-ray antideuteron workshop, which was held at UCLA in June 2014. It reviews broad classes of dark matter candidates that result in detectable cosmic-ray antideuteron fluxes, as well as the status and prospects of current experimental searches. The coalescence model of antideuteron production and the influence of antideuteron measurements at particle colliders are discussed. This is followed by a review of the modeling of antideuteron propagation through the magnetic fields, plasma currents, and molecular material of our Galaxy, the solar system, the Earths geomagnetic field, and the atmosphere. Finally, the three ongoing or planned experiments that are sensitive to cosmic-ray antideuterons, BESS, AMS-02, and GAPS, are detailed. As cosmic-ray antideuteron detection is a rare event search, multiple experiments with orthogonal techniques and backgrounds are essential. Many theoretical and experimental groups have contributed to these studies over the last decade, this review aims to provide the first coherent discussion of the relevant dark matter theories that antideuterons probe, the challenges to predictions and interpretations of antideuteron signals, and the experimental efforts toward cosmic antideuteron detection.