If $\sqrt{a}-\sqrt{b}$ is a root of a polynomial with integer coefficients, then so is $\sqrt{a}+\sqrt{b}$. 
If $\sqrt{a} - \sqrt{b}$, where $a$ and $b$ are positive integers and non-perfect squares, is a root of a polynomial with integer coefficients, then $\sqrt{a} + \sqrt{b}$ also is.

It seems to hold some relationship with the quadratic formula. However, I have no idea on how to prove it.

Returning to this question to complete my work in my previous answer - the crucial insight to the following argument was provided by the answer of @robjohn.

Supposing $a$, $b$ are positive integers, $a \neq b$ such that none of $a$, $b$, $ab$ are perfect squares, then for any polynomial with integer coefficients $p(x)$, it holds that $p(\sqrt a - \sqrt b) = 0 \implies p(\sqrt a + \sqrt b) = 0$

The necessary lemma, already argued by @robjohn, is that $1$, $\sqrt a$, $\sqrt b$, and $\sqrt {ab}$ are all linearly independent over $\mathbb Q$. That is, if $A,B,C,D$ are rationals such that $A + B\sqrt a + C\sqrt b + D\sqrt{ab} = 0$, then $A = B = C = D = 0$.
To complete the work I presented in my previous answer, I shall prove

There is no nonzero polynomial $r(x)$ of degree at most $3$ with rational coefficients such that $r(\sqrt a - \sqrt b) = 0$.

In which case $H(x) = (x^2 - a - b)^2 - 4ab$ is the unique monic polynomial of minimal degree for which $H(\sqrt a - \sqrt b) = 0$. Then, the observation that $H(\sqrt a + \sqrt b) = 0$ and an argument via the polynomial division algorithm finishes the problem.
I have shown before that there is no nonzero degree $1$ polynomial $r(x)$ such that $r(\sqrt a - \sqrt b) = 0$. For the quadratic case, suppose $r(x) = Ax^2 + Bx + C$ is a polynomial with integer coefficients such that $r(\sqrt a - \sqrt b) = 0$. By expanding the equation $A(\sqrt a - \sqrt b)^2 + B(\sqrt a - \sqrt b) + C = 0$, we can conclude
$$(Aa + Ab + C) + B \sqrt a - B \sqrt b - 2A \sqrt{ab} = 0$$
From the lemma above, we conclude in particular that $B = 0$. However this also implies
$$2A\sqrt{ab} = Aa + Ab + C$$
which implies $\sqrt{ab}$ is rational (and must therefore be an integer), contradicting the assumption that $ab$ is not a square.

Finally, turning to the cubic case. Suppose $r(x)$ is a polynomial of degree $3$ such that $r(\sqrt a - \sqrt b) = 0$. Without loss of generality $r(x)$ has rational coefficients and is monic, in which case $r(x) = x^3 + Ax^2 + Bx + C$ for rational $A$, $B$, $C$. Expanding
$$(\sqrt a - \sqrt b)^3+A(\sqrt a - \sqrt b)^2 + B(\sqrt a - \sqrt b) + C = 0$$
and applying the linear independence of $1$, $\sqrt a$, $\sqrt b$, and $\sqrt {ab}$ over $\mathbb Q$ leads to the following linear system of equations for $A$, $B$, and $C$.
\begin{array}{rlc}
Aa + Ab + C & =0 \quad & (1)\\
a + 3b + B &=0 & (\sqrt a) \\
-3a - b - B &=0 & (\sqrt b) \\
-2A &=0 & (\sqrt{ab})
\end{array}
From the fourth equation $A = 0$, which implies by the first equation $C = 0$. But if $C = 0$ then $\frac{r(x)}{x}$ is a rational polynomial of degree $2$ with a root at $x = \sqrt a - \sqrt b \neq 0$, contradicting the previous argument. This finishes the problem.
