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.

(Let's agree first that $a, b \ge 0$, so that $\sqrt{a}$ and $\sqrt{b}$ are real and sensible)
This statement:

For any polynomial $p(x) \in \Bbb{Z}[x]$, if $p(\sqrt{a} - \sqrt{b}) = 0$ then $p(\sqrt{a} + \sqrt{b}) = 0$

is in general false, with the easiest counter example probably being $a = b = 1,\ p(x) = x$. But that's no fun as an answer, so here is an almost-classification of every situation in which this statement is true:
$1)$ Firstly, if $b = 0$ then the statement holds $\forall a$, because then $p(\sqrt{a} - \sqrt{b}) = p(\sqrt{a} + \sqrt{b}) = p(\sqrt{a})$

$2)$ So now suppose $b \ne 0$, in which case $b \gt 0$. If $b$ is a square (ie: $\sqrt{b} \in \Bbb{Z}$), then the statement never holds, because of the counterexample where $p(x) = \left(x + \sqrt{b}\right)^2 -a$, which is an integer-coefficient polynomial by the assumption that $\sqrt{b} \in \Bbb{Z}$. In this case, $p(\sqrt{a} - \sqrt{b}) = 0$ but $p(\sqrt{a} + \sqrt{b}) = 4 \sqrt{ab} + 4b \ge 4b \gt 0$

$3)$ So now suppose $b \ne 0$ and that $b$ is not a square (ie $\sqrt{b} \not\in \Bbb{Z}$). If $a$ is a square ($\sqrt{a} \in \Bbb{Z}$), then surprisingly the statement always holds. Here is why:
Suppose $p(\sqrt{a} - \sqrt{b}) = 0$ for some $p$ - polynomial with integer coefficients. It is sufficient actually to consider polynomials with rational coefficients, as someone observed in the comments, in which case we can use the division algorithm. Specifically, to divide $p(x)$ by the polynomial $h(x) = \left(x - \sqrt{a}\right)^2 - b$ 
(Observe that $h(x)$ has both $\sqrt{a} - \sqrt{b}$ and $\sqrt{a} + \sqrt{b}$ as roots). Then we obtain $p(x) = h(x)q(x) + r(x)$ for some rational-coefficient polynomials $q, r$ and where $r$ is a polynomial of degree $1$. Now, $r(\sqrt{a} - \sqrt{b}) = 0$ by staring at the equation $p(x) = h(x)q(x) + r(x)$
Since $r$ is a degree $1$ polynomial we have $m(\sqrt{a} - \sqrt{b}) + n = 0$ for some rational $m, n$. But actually, this is impossible unless $m = n = 0$, because if $m \ne 0$ then $\sqrt{b} = {m\sqrt{a} + n \over m}$, which implies $\sqrt{b}$ is rational (remember in this case we are assuming $\sqrt{a} \in \Bbb{Z}$), and this is impossible because $b$ is not a square, in which case $\sqrt{b}$ must be irrational. And if $m = 0$, then $n = 0$ too by plugging in.
In which case, $p(x) = h(x)q(x) + 0$, and therefore $p(\sqrt{a} + \sqrt{b}) = h(\sqrt{a} + \sqrt{b})q(\sqrt{a} + \sqrt{b}) = 0$.

$4)$ Then the next case is $b \ne 0$, $b$ not a square and $a$ not a square (in particular, $a \ne 0$  as well). This case again has two more subcases: namely if $ab$ is a square or not.
Because if $ab$ is a square, then the statement never holds because of this counterexample: $p(x) = x^2 - a + 2\sqrt{ab} - b$. Then $p(\sqrt{a} - \sqrt{b}) = 0$, but $p(\sqrt{a} + \sqrt{b}) = 4\sqrt{ab} \gt 0$ since $a$ and $b$ are both positive.

$5)$ So now suppose $b \ne 0$, $b, a, ab$ all not squares. You guessed it - two more subcases. If $a = b$ then the statement never holds, by the example $p(x) = x$. This case was necessary to weed out for certain steps in the last case (we need to know that $\sqrt{a} - \sqrt{b} \ne 0$).

$6)$ Which brings me to the final case I was able to stomach before I had to put my pen down: the case where $b \ne 0$, $b, a, ab$ all not squares, and $a \ne b$. I suspect that in this case, the statement will always hold, which would be the complete classification of solutions to when the statement holds, and be the end of the problem.
Here is why I think so: start with $x = \sqrt{a} = \sqrt{b}$. If your goal is to kill $x$ with an integer-coefficient polynomial, then it seems that these are the optimal steps you would want to take:
$\begin{align}
x = \sqrt{a} - \sqrt{b}\\
& \implies x^2 = a - 2\sqrt{ab} + b\\
& \implies x^2 -a -b = 2\sqrt{ab}\\
& \implies (x^2 -a -b)^2 = 4ab\\
& \implies (x^2 -a -b)^2 - 4ab = 0
\end{align}$
Let's call the polynomial that is written in the last step there $H(x)$. The idea is that this has to be the "minimal killing polynomial" of $\sqrt{a} - \sqrt{b}$.
Observe that in the earlier cases - specifically in the construction of $h(x)$ from case $3)$ - $H(x)$ was not minimal - we were able to use other tricks and facts to stop this process early (ie: if $\sqrt{a}, \sqrt{b}, \sqrt{ab}$ were themselves integers, then we could take advantage of that and get a smaller killing polynomial - smaller than this fourth-degree monster, at any rate).
Observe also that not only does $H(x)$ kill $\sqrt{a} - \sqrt{b}$, but it also kills $\sqrt{a} + \sqrt{b}$. This property was also shared by $h(x)$ in case $3)$, which was the crux of that whole argument - in case $3)$, $h(x)$ turned out to be minimal, in the sense that it necessarily had to be a factor of any polynomial that killed $\sqrt{a} - \sqrt{b}$, which implied that the polynomial also killed $\sqrt{a} + \sqrt{b}$
So if $H(x)$ is minimal in this case, case $6)$, and if $H(x)$ must be a factor of any $p(x)$ with $p(\sqrt{a} - \sqrt{b}) = 0$, then we will finally be done.
So, consider an arbitrary killing polynomial $p(x)$ and divide by $H$ - in which case we have $p(x) = H(x)q(x) + r(x)$. This problem is much harder than in case $3)$, because since $H$ is of degree four, then $r(x)$ is some arbitrary cubic polynomial - totally unwieldy. But if you can prove that, under the circumstances of case $6)$, it is impossible for a cubic to kill $\sqrt{a} - \sqrt{b}$, then $r(x)$ will necessarily have to be $0$, in which case we are done.
I proved that in this case too it is impossible for a degree $1$ polynomial to kill $\sqrt{a} - \sqrt{b}$, and I attempted the quadratic case too, but it turned out to be too much for the room I had on my scratch paper. The process involves deriving some sort of contradiction (showing that one of $\sqrt{a}, \sqrt{b}, \sqrt{ab}$ must be rational)
Here is the degree $1$ proof: suppose again that $m(\sqrt{a} - \sqrt{b}) + n = 0$ for some rational $m, n$. Note that if either of $m$ or $n$ are $0$, then in fact $m = n = 0$ (this is where we use the assumption that $a \ne b$ which implies $\sqrt{a} - \sqrt{b} \ne 0$).
Then a nontrivial sol'n would have both $m \ne 0 \ne n$, in which case rewrite the eqn as $m\sqrt{a} + n = m\sqrt{b}$ and square both sides to obtain $m^2 + 2mn\sqrt{a} + n^2 = m^2b$, from which we obtain $\sqrt{a} = {m^2b - m^n - n^2 \over 2mn}$ which is rational, contradicting again that $a$ is not a square and therefore $\sqrt{a}$ is irrational. Thus, we know the case of $r(x)$ being a degree 1 polynomial is impossible.
I won't write what I attempted for the quadratic case, just know that it involves a lot of squaring and algebra. But I suspect that this process can be continued all the way through to $r(x)$ - degree $3$
