Bombarding a solid surface with a broad ion beam can produce a remarkable variety of nanoscale patterns. The spontaneous emergence of these patterns is not just fascinating in its own right, since in the future ion bombardment may prove to be an important tool in the fabrication of nanostructures. As an introduction to the field, the question of why oblique-incidence ion bombardment often produces periodic height modulations or " ripples " on a solid surface will be addressed. I will then move on to discuss a theory we have developed that explains the genesis of the strikingly regular hexagonal arrays of nanodots that can form when a flat surface of a binary compound is subjected to normal-incidence ion bombardment. As we have demonstrated analytically, nanodot arrays with short-range hexagonal order emerge spontaneously for a certain range of the parameters. In our theory, the coupling between the topography and a thin surface layer of altered stoichiometry is the key to the pattern formation.