In the past decade, high performance batteries based on mobile Li+ ions in layered metal oxides such as LixCoO2 have made possible a revolution in mobile electronic technology, from iPods to mobile phones. Structurally similar NaxCoO2 has emerged as a system of fundamental scientific interest because of its highly unusual electrical and magnetic properties. The density, x, of sodium in the intercalation layers can be altered electrochemically, directly changing the number of conduction electrons on metallic CoO2 sheets. Using neutron diffraction we have detected long-range three-dimensional ordering of Na+ ions in single crystals of x=0.78 and 0.92 and demonstrate a remarkable concentration dependence of Na+ ordering and vacancy clustering. Large scale numerical simulations show clustering of charged droplets that then order long range. The multivacancy clusters form cages resulting in high thermopower for NaxCoO2 and their ordering induces a periodic potential in the CoO2 that readily explains many of the observed electrical and magnetic properties. Electrochemical control of nanoscale devices has great technological potential. Here we show that NaxCoO2 provides a model system for exploration.