Recently, semiconductor nanostructures have shown significant promise for a wide range of electronic, optoelectronic, and magnetic applications. In this talk, I will discuss the formation mechanisms of a variety of semiconductor nanostructures, including phase separation-induced alloy nanostructures and strain-induced self-assembled quantum dots. I will show how we have used data from cross-sectional scanning tunneling microscopy, in conjunction with x-ray reciprocal space maps, to develop new models for self-ordering of InAs/GaAs quantum dot superlattices@footnote 1@ and spontaneous lateral phase separation in InAlAs alloys.@footnote 2@ I will also describe our recent investigations of the role of elastic anisotropy in semiconductor nanopatterning, towards the formation of three-dimensional quantum dot crystals. These mechanisms are likely to be applicable to a wide range of heteroepitaxial semiconductor nanostructures. @FootnoteText@This work was supported in part by the National Science Foundation (CAREER Award and Nanoscale Exploratory Research Program) and the Army Research Office (MURI Program) @footnote 1@ B. Lita, R.S. Goldman, et al, Appl. Phys. Lett. 75, 2797 (1999); Surface Review and Letters 7, 539 (2000). @footnote 2@ B. Shin, A. Lin, K. Lappo, R.S. Goldman, et al Appl. Phys. Lett . 80, 3292 (2002).