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?.
For new results, in integer multiplication, check the breakthrough paper by: David Harvey, and Joris Van Der Hoeven, et al . Integer multiplicaion in $O(n*(log$ $n))$. This proves Schonhage Strassens' conjecture from the 1970s that integer multiplication is really possible in $O(n*(log$ $n))$. From, straightforward (school) integer multiplication which is $O( n^{2}) $, to karatsubas' algorithm which is $O(n^{1.58})$, to $O(n*(log$ $n))$, by above authors. The authors use the property of specific multivariate polynomial rings that admit efficient multiplication.
The authors show that integer multiplication (which is one dimensional) could be represented in a setting of a specific multivariate polynomial ring. Starting with a binary representation of integers, begin with the fixed point coordinate vectors(to a precision), and then go on to utilize them in coefficient rings for that polynomial representation. One could select parameters, and reduce the integer multiplication problem to one of convolution over a ring with a specific structure, reaching the bound.
The bound is a significant improvement over earlier algorithms, and with many digits the efficiencies are apparent, for a large number of digits billions, and larger scales as author(s) claim its unknown, but good performance is possible.
Best Answer
This answer is meant to answer only your second question.
Claim. Let $K=\mathbb{Q}(\sqrt[3]{2})$ and $\alpha = \sqrt[3]{2}-\sqrt[3]{4} \in K$. Then there does not exist $\beta \in K$ such that $\beta^2-\alpha \in \mathbb{Q}$.
More generally, any square in $K=\mathbb{Q}(\sqrt[3]{d})$ is of the form $$ (x+y\sqrt[3]{d}+z\sqrt[3]{d^2})^2=x^2+2dyz+(2xy+dz^2)\sqrt[3]{d}+(y^2+2xz)\sqrt[3]{d^2}. $$ So, if for every $\alpha \in K$ there exists $\beta \in K$ such that $\beta^2-\alpha \in \mathbb{Q}$, that means that for every $b,c \in \mathbb{Q}$ there exist $x,y,z \in \mathbb{Q}$ satisfying $$ 2xy+dz^2 = b,~~y^2+2xz=c. $$ This is an intersection of two quadrics in three-dimensional space, which defines a curve of genus $1$ if it is non-singular. Eliminating $x$, we obtain $$ bz-dz^3=cy-y^3, $$ which is a plane cubic curve with the rational point $P=(0,0)$ on it (which on the intersection of the two quadrics corresponds to the point at infinity).
In fact $P$ is a flex or inflection point, meaning that the tangent to $P$ (which is simply given by the linear part of the equation of the curve, so by $cy-bz=0$) has intersection multiplicity $3$. Considering the equation of the cubic in homogeneous form, $$ bX^2Z-dZ^3=cX^2Y-Y^3, $$ the coordinates of the point $P$ are now $(1:0:0)$ and its tangent is $cY-bZ=0$. If you look in Cassels' book on elliptic curves, you find that you can transform a cubic with a flex $P$ into Weierstrass form by a linear transformation which maps $P$ to the point $(0:1:0)$ and its tangent to the line $Z=0$. The first can be achieved by just interchanging the roles of $X$ and $Y$, i.e. by considering the new curve $$ bY^2Z-dZ^3=cXY^2-X^3, $$ where now the point $P$ has coordinates $(0:1:0)$ and tangent equal to $cX-bZ=0$. If we further replace $Z$ by $(cX-Z)/b$, we will obtain a Weierstrass curve (up to a simple scaling of $X$ and $Y$). The substitution $Z \mapsto (cX-Z)/b$ yields $Y^2(cX-Z)-d(cX-Z)^3/b^3=cXY^2-X^3$, where you already see the $XY^2$ terms cancelling each other, producing the equation $-b^3 Y^2Z - d(cX-Z)^3=-b^3 X^3$, or after rearranging terms $b^3 Y^2Z = b^3 X^3 - d(cX-Z)^3$. Now we change back to affine coordinates $x$ and $y$, and we obtain $b^3 y^2 = b^3 x^3 - d(cx-1)^3$. We expand and collect the cubic terms: $$ b^3 y^2 = (b^3- c^3d) x^3 + 3c^2dx^2 - 3cdx + d. $$ We get rid of the coefficients of the highest powers in $x$ and $y$ by multiplying everything by $b^3(b^3- c^3d)^2$ and replacing $x \mapsto x/(b(b^3- c^3d))$ and $y \mapsto y/(b^3(b^3- c^3d))$. We then get: $$ y^2 = x^3 + 3bc^2dx^2 - 3b^2cd(b^3- c^3d)x + b^3d(b^3- c^3d)^2. $$ Now this is a Weierstrass curve which is isomorphic (even projectively equivalent) to the cubic curve we started with, so in the case where it has no other points except $(0:1:0)$, we will know that the original system of two quadratics has no solutions. (Also conversely, if it does have non-trivial points, then the system does have a solution.)
For this, we can use for example Sage. When we do that, for example putting as I did $d=2$, $b=1$, $c=-1$, we will find that the resulting Weierstrass curve is $y^2=x^3+6x^2+18x+18$, and that its group of rational points is the trivial group. $\square$
The answer to the part "How does one determine whether there exists $\beta$ such that $\beta^2-\alpha \in \mathbb{Q}$?" probably has to be that one simply has to solve the equations (which means finding points on a curve given as the intersection of $d-1$ quadrics in $d$-dimensional space). I don't think there is anything else for it. Even in the degree $3$ case there seems to be no short-cut available.