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)CoO2o1.25(2)D2O and its anhydrous parent compound Na0.61(1)CoO2. The deuterate superconducting compound is formed by coordinating four D2O molecules (two above and two below) to each Na ion in a way that gives Na-O distances nearly equal to those in the parent compound. One deuteron of the D2O molecule is hydrogen bonded to an oxygen atom in the CoO2 plane and the oxygen atom and the second deuteron of each D2O molecule lie approximately in a plane between the Na layer and the CoO2 layers. This coordination of Na by four D2O molecules leads to ordering of the Na ions and D2O molecules. The sample studied here, which has Tc=4.5 K, has a refined composition of Na0.31(3)CoO2o1.25(2)D2O, in agreement with the expected 1:4 ratio of Na to D2O. These results show that the optimal superconducting composition should be viewed as a specific hydrated compound, not a solid solution of Na and D2O (H2O) in NaxCoO2oyD2O. Studies of physical properties vs. Na or D2O 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.