Neutron and x-ray powder diffraction have been used to investigate the crystal structures of a sample of the newly-discovered superconducting sodium cobaltate deuterate compound with composition Na0.31(3)CoO2\ensuremath1.25(2)D2O{\mathrm{Na}}_{0.31(3)}{\mathrm{CoO}}_{2}\ensuremath{\cdot}1.25(2){\mathrm{D}}_{2}\mathrm{O} and its anhydrous parent compound Na0.61(1)CoO2.{\mathrm{Na}}_{0.61(1)}{\mathrm{CoO}}_{2}. The anhydrous parent compound Na0.61(1)CoO2{\mathrm{Na}}_{0.61(1)}{\mathrm{CoO}}_{2} has two partially occupied Na sites sandwiched, in the same plane, between CoO2{\mathrm{CoO}}_{2} layers. When Na is removed to make the superconducting composition, the Na site that experiences the strongest Na--Co repulsion is emptied while the occupancy of the other Na site is reduced to about one third. The deuterate superconducting compound is formed by coordinating four D2O{\mathrm{D}}_{2}\mathrm{O} molecules (two above and two below) to each remaining Na ion in a way that gives Na--O distances nearly equal to those in the parent compound. One deuteron of the D2O{\mathrm{D}}_{2}\mathrm{O} molecule is hydrogen bonded to an oxygen atom in the CoO2{\mathrm{CoO}}_{2} plane and the oxygen atom and the second deuteron of each D2O{\mathrm{D}}_{2}\mathrm{O} molecule lie approximately in a plane between the Na layer and the CoO2{\mathrm{CoO}}_{2} layers. This coordination of Na by four D2O{\mathrm{D}}_{2}\mathrm{O} molecules leads in a straightforward way to ordering of the Na ions and D2O{\mathrm{D}}_{2}\mathrm{O} molecules consistent with the observation of additional shorter-range scattering features in the diffraction data. The sample studied here, which has Tc=4.5K,{T}_{c}=4.5\mathrm{K}, has a refined composition of Na0.31(3)CoO2\ensuremath1.25(2)D2O,{\mathrm{Na}}_{0.31(3)}{\mathrm{CoO}}_{2}\ensuremath{\cdot}1.25(2){\mathrm{D}}_{2}\mathrm{O}, in agreement with the expected 1:4 ratio of Na to D2O.{\mathrm{D}}_{2}\mathrm{O}. These results show that the optimal superconducting composition should be viewed as a specific hydrated compound, not a solid solution of Na and D2O{\mathrm{D}}_{2}\mathrm{O} (H2O)({\mathrm{H}}_{2}\mathrm{O}) in NaxCoO2\ensuremathD2O.{\mathrm{Na}}_{x}{\mathrm{CoO}}_{2}\ensuremath{\cdot}{\mathrm{D}}_{2}\mathrm{O}. The hydrated superconducting compound may be stable over a limited range of Na and D2O{\mathrm{D}}_{2}\mathrm{O} concentration, but studies of Tc{T}_{c} and other physical properties vs Na or D2O{\mathrm{D}}_{2}\mathrm{O} composition should be viewed with caution until it is verified that the compound remains in the same phase over the composition range of the study.