Zev, when $[K:{\mathbf Q}] > 2$, finding all $\alpha$ which are ring generators for ${\mathcal O}_K$ is a hard problem in general: there are only finitely many choices modulo the obvious condition that if
$\alpha$ works then so does $a + \alpha$ for any integer $a$. In other words, up to adding an integer there are only finitely many possible choices -- which could of course mean there are no choices.

Here is a nice example: what are the possible ring generators for the integers of ${\mathbf Q}(\sqrt[3]{2})$? We know a basis for the ring of integers is $1, \sqrt[3]{2}, \sqrt[3]{4}$, so a ring generator over $\mathbf Z$ would, up to addition by an integer, have the form $\alpha_{x,y} = x\sqrt[3]{2} + y\sqrt[3]{4}$ for some integers $x$ and $y$ which are not both 0. The index of the ring ${\mathbf Z}[\alpha_{x,y}]$ in the full ring of integers is the absolute value of the determinant of the matrix expressing $1, \alpha_{x,y}, \alpha_{x,y}^2$ in terms of $1, \sqrt[3]{2},\sqrt[3]{4}$, and after a computation that turns out to be $|x^3 - 2y^3|$. We want this to be 1 in order to have a ring generator, which means we have to find all the integral solutions to the equation $x^3 - 2y^3 = \pm 1$. Well, that's a pretty famous example of an equation with only finitely many integral solutions. Up to sign the only solutions are $(1,0)$ and $(1,1)$, so $\alpha_{x,y}$ is $\sqrt[3]{2}$ or $\sqrt[3]{2} + \sqrt[3]{4}$ up to sign (and then addition by an integer).

Here's a more general cubic exercise, just to put the previous example in some perspective (among concrete examples). Let ${\mathbf Q}(\alpha)$ be a cubic field where $\alpha^3 + b\alpha + c = 0$ for integers $b$ and $c$.

a) Show for $x, y \in {\mathbf Z}$ not both 0 that $[{\mathbf Z}[\alpha]:{\mathbf Z}[x\alpha + y\alpha^2]] = |x^3 + bxy^2 + cy^3|$. Therefore if $1,\alpha,\alpha^2$ is known to be a ${\mathbf Z}$-basis of the ring of integers, finding all other ring generators besides $\alpha$, up to addition by integers, amounts to solving $x^3 + bxy^2 + cy^3 = \pm 1$ in integers.

b) It is natural to guess from part a that if $\alpha^3 + a\alpha^2 + b\alpha + c = 0$ and $x, y \in {\mathbf Z}$ are not both 0 the index
$[{\mathbf Z}[\alpha]:{\mathbf Z}[x\alpha + y\alpha^2]]$ should be $|x^3 + ax^2y + bxy^2 + cy^3|$. Decide if that natural guess is right!

In general, finding all possible ring generators (modulo addition by an integer) for the ring of integers in a number field amounts to solving some norm-form equation equal to $\pm 1$, and beyond the quadratic case that kind of equation will have just a finite number of integral solutions. A place to look for further discussion is Narkiewicz's massive tome on algebraic number theory: pp. 64--65 and especially p. 80. It turns out the question of finiteness of the number of possible ring generators up to addition by an integer goes back to Nagell. The general case was settled by Gyory in 1973; see MathSciNet MR0437489.

There's actually a whole book on this theme: Diophantine Equations and Power Integral Bases by István Gaál, Birkhauser, 2002.

Update in 2018: to address your question about finding a ring of integers needing many generators as a $\mathbf Z$-algebra (not just as a $\mathbf Z$-module), see my answer at Explicit family of number rings $\mathcal{O}_{K_n}$ requiring $n$ generators?.

cubicwith $2$ totally split; proof: $\mathbf{Z}[x]$ has < 3 maps to $\mathbf{F}_ 2$! – BCnrd Apr 13 '10 at 22:18notmonogenic: any number field whose different ideal is not principal. Of course there is then the task of coming up with examples by that method... – KConrad Apr 14 '10 at 2:01exactlythe same as the old version inside. They just photocopied it! The only differences are a new cover, 8 pages of typos, and a blurb at the front mentioning you and Keith in the same sentence as Serre :-) – Kevin Buzzard Apr 14 '10 at 8:37