At the low temperatures ($sim$10 K) and high densities ($sim$100,000 H$_2$ molecules per cc) of molecular cloud cores and protostellar envelopes, a large amount of molecular species (in particular those containing C and O) freeze-out onto dust grain surfaces. It is in these regions that the deuteration of H$_3^+$ becomes very efficient, with a sharp abundance increase of H$_2$D$^+$ and D$_2$H$^+$. The multi-deuterated forms of H$_3^+$ participate in an active chemistry: (i) their collision with neutral species produces deuterated molecules such as the commonly observed N$_2$D$^+$, DCO$^+$ and multi-deuterated NH$_3$; (ii) their dissociative electronic recombination increases the D/H atomic ratio by several orders of magnitude above the D cosmic abundance, thus allowing deuteration of molecules (e.g. CH$_3$OH and H$_2$O) on the surface of dust grains. Deuterated molecules are the main diagnostic tools of dense and cold interstellar clouds, where the first steps toward star and protoplanetary disk formation take place. Recent observations of deuterated molecules are reviewed and discussed in view of astrochemical models inclusive of spin-state chemistry. We present a new comparison between models based on complete scrambling (to calculate branching ratio tables for reactions between chemical species that include protons and/or deuterons) and models based on non-scrambling (proton hop) methods, showing that the latter best agree with observations of NH$_3$ deuterated isotopologues and their different nuclear spin symmetry states.