When there is a sequence of transitions separating a ordered (broken symmetry) “crystalline state” from a disordered “fluid” state, the intermediate phases which spontaneously break a subset of the symmetries of the of the crystalline state can be said to have “vestigial order.” Familiar examples from classical physics include hexatic phases in the theory of 2D melting and nearly smectic nematic phases in 3D. Here, in the context of the phases of highly correlated electronic materials, we analyze a solvable O(N) quantum rotor model of the formation of an electron-nematic phase through the partial melting of a unidirectional (striped) density wave phase by thermal or quantum fluctuations, or as a function of increasing quenched disorder. We comment on the relevance of these considerations to the formation of nematic phases in the cuprates, Fe-pnictides, Sr$_3$Ru$_2$O$_7$, and quantum Hall systems, as well as for a possible electron cholesteric phase in the cuprates.