We present a combined high-energy x-ray diffraction and local-density approximation study of the sodium ordering in Na0.75CoO2. The obtained results rule out previously proposed Na-ordering models and provide strong evidence for the formation of sodium-density stripes in this material. The local-density approximation calculations prove that the sodium-density stripes lead to a sizable dip in the density of the Co states at the Fermi level, pointing to band structure effects as a driving force for the stripe formation. This indicates that the sodium ordering is connected to stripelike charge correlations within the CoO2 layers, leading to an astonishing similarity between the doped cuprates and the NaxCoO2 compounds.