This question is related to Degree of sum of algebraic numbers and algebraic numbers of degree 3 and 6, whose sum has degree 12. In this last question I asked a very special case of the following problem : given two algebraic numbers $\alpha$ and $\beta$ with degrees $a$ and $b$ respectively, what can the degree of $\alpha+\beta$ be ?
I believe the answer is as follows : the degree of $\alpha+\beta$ can equal some value $d$ iff
(1) $d \leq ab$ and $a \leq db$ and $b \leq da$. (this condition is obviously necessary)
(2) $d$ divides $ab$, or $a$ divides $db$, or $b$ divides $da$.
The "if" part probably involves Galois theory as in Gerry's answer to the special case.
EDIT 07/01/2010 : As Gerry noted, the conjecture above is grossly false. Below is a "corrected version" of my conjecture.
I believe the answer is as follows : the degree of $\alpha+\beta$ can equal some value $d$ iff
(*) There is some integer $e$ divisible by all of $a,b,d$, and lower than or equal to all of $ab,ad,bd$ (this is a necessary condition, as is seen by taking $e$ to be the degree of the extension $k(\alpha,\beta)/k$, where $k$ is the base field).