Co3V2O8 (CVO) has a geometrically frustrated magnetic lattice, a Kagome staircase. The crystal structure consists of two inequivalent Co sites, one-dimensional chains of Co(2) spine sites, linked by Co(1) cross-tie sites. Neutron powder diffraction has been used to solve the basic magnetic and crystal structures of this system, while polarized and unpolarized single crystal diffraction measurements have been used to reveal a variety of incommensurate phases, interspersed with lock-in transitions to commensurate phases. CVO initially orders magnetically at 11.3 K into an incommensurate, transversely polarized, spin density wave state, with wave vector k=(0,delta,0) with delta=0.55 and the spin direction along the a axis. Delta is found to decrease monotonically with decreasing temperature, and then it locks into a commensurate antiferromagnetic structure with delta=0.5 for 6.9<T<8.6 K. Below 6.9 K the magnetic structure becomes incommensurate again. Delta continues to decrease with decreasing temperature, and locks-in again at delta=1/3 over a narrow temperature range (6.2<T<6.5 K). The system then undergoes a strongly first order transition to the ferromagnetic ground state (delta=0) at Tc=6.2 K. A dielectric anomaly is observed around the ferromagnetic transition temperature of 6.2 K, demonstrating a significant spin-charge coupling present in CVO. A theory based on group theory analysis and a minimal Ising model with competing exchange interactions can explain the basic features of the magnetic ordering.