How can the correct form of the partial fractions decomposition be found for arbitrary rational functions? What is the reasoning or intuition that leads to the assumption that 
$$r(x) =\frac{x^2 + 2}{ (x+2)(x-1)^2}$$ 
can be expressed as 
$$r(x) = \frac{A}{x-1} + \frac{B}{(x-1)^2} + \frac{C}{x+2}$$
(For the sake of context, this problem arose when trying to solve an integral by the method of partial fractions.)
Moreover, how can the correct form of the partial fractions decomposition be found for other rational functions?

Start with the rational function $\frac{N(x)}{D(x)},$ where $N(x)$ and $D(x)$ are polynomials over whichever field we happen to be working in (such as the real numbers or complex numbers) and the degree of $N(x)$ is less than the degree of $D(x).$
Consequences of Bezout's Identity
Suppose we can factor $D(x) = P_1(x)P_2(x),$ where $P_1(x)$ and $P_2(x)$ have no common factor (and therefore no common root).
Then by Bezout's theorem for polynomials (aka Bezout's identity for polynomials), there are polynomials $F_1(x)$ and $F_2(x)$ such that $F_1(x)P_1(x) + F_2(x)P_2(x) = 1.$
(I believe the application of Bezout's identity here is why calculus books give the technique of partial fraction decomposition without proof. Bezout's identity comes from abstract algebra, which normally is not taught until you've had at least a couple of years of calculus; you wouldn't normally see it before university, and even then you'd probably only see it if you majored in math. Personally, I think it's a shame the curriculum is sequenced this way--I spent most of my time in first-year calculus griping about why we needed to memorize all that ugly ____, and only a few years later, when I finally got to the upper level courses, realized it was actually beautiful and made perfect sense--but that's enough ranting for one answer.)
By polynomial division we also have
\begin{align}
N(x)F_1(x) &= Q_2(x)P_2(x) + R_2(x), \\
N(x)F_2(x) &= Q_1(x)P_1(x) + R_1(x)
\end{align}
where the degree of $R_i(x)$ is less than the degree of $P_i(x).$
Therefore
\begin{align}
N(x) &= N(x)(F_1(x)P_1(x) + F_2(x)P_2(x)) \\
&= N(x)F_1(x)P_1(x) + N(x)F_2(x)P_2(x) \\
&= Q_2(x)P_1(x)P_2(x) + P_1(x)R_2(x) + Q_1(x)P_1(x)P_2(x) + P_2(x)R_1(x) \\
&= (Q_1(x) + Q_2(x))P_1(x)P_2(x) + P_1(x)R_2(x) + P_2(x)R_1(x).
\end{align}
Since $\deg(R_1(x)) < \deg(P_1(x))$ and $\deg(R_2(x)) < \deg(P_2(x)),$
it follows that $\deg(P_2(x)R_1(x)) < \deg(P_1(x)P_2(x))$ 
and $\deg(P_1(x)R_2(x)) < \deg(P_1(x)P_2(x)).$
Since we must also have $\deg(N(x)) < \deg(P_1(x)P_2(x)),$
we must have $\deg((Q_1(x) + Q_2(x))P_1(x)P_2(x)) < \deg(P_1(x)P_2(x)),$
which is possible only if $Q_1(x) + Q_2(x) = 0.$
Therefore we can more simply write
$$ N(x) = P_1(x)R_2(x) + P_2(x)R_1(x).$$
Therefore
\begin{align}
 \frac{N(x)}{D(x)} &= \frac{P_1(x)R_2(x) + P_2(x)R_1(x)}{P_1(x)P_2(x)} \\
&= \frac{R_2(x)}{P_2(x)} + \frac{R_1(x)}{P_1(x)}.  \tag1
\end{align}
Taking out a first-degree factor
To apply this to partial fraction decomposition, if $x - a$ divides $D(x)$
we find the greatest power of $x - a$ that divides $D(x).$
Suppose that this is the $n$th power.
Set $P_1(x) = (x - a)^n$ and $P_2(x) = \frac{D(x)}{(x - a)^n}.$
Then $P_1(x)$ and  $P_2(x)$ have no common factor, and the result $(1)$ above says that
$$
 \frac{N(x)}{D(x)} = \frac{R_2(x)}{P_2(x)} + \frac{R_1(x)}{(x - a)^n}
$$
where $\deg(R_2(x)) < \deg(P_2(x))$ and $\deg(R_1(x)) < n = \deg((x - a)^n).$
Taking out an irreducible quadratic factor
If we are doing real analysis and don't allow polynomials to have complex coefficients, then $D(x)$ might have a factor of the form $x^2 + bx + c$
that cannot be factored into first-degree polynomials (that is, it is irreducible).
In that case, if the highest power of $x^2 + bx + c$ that divides $D(x)$ is the $m$th power, then we can write $P_1(x) = (x^2 + bx + c)^m$ and 
$P_2(x) = \frac{D(x)}{(x^2 + bx + c)^m}.$
It follows that $P_1(x)$ and  $P_2(x)$ have no common factor, and therefore (according to $(1)$ again)
$$
 \frac{N(x)}{D(x)} = \frac{R_2(x)}{P_2(x)} + \frac{R_1(x)}{(x^2 + bx + c)^m}
$$
where $\deg(R_2(x)) < \deg(P_2(x))$ and $\deg(R_1(x)) < 2m = \deg((x^2 + bx + c)^m).$
Completing the decomposition
Provided that we are able to find all the first- and second-degree factors of the polynomial $D(x),$ we can repeatedly take out either first-degree factors or irreducible quadratic factors from $D(x)$ and then from the polynomial $P_2(x)$ that we get after taking out the previous factor, until we end up with a $P_2$ that is itself a first-degree polynomial or an irreducible quadratic.
We end up with something that looks like this:
$$
\frac{N(x)}{D(x)} = \frac{S_1(x)}{(x - a_1)^{n_1}} + \cdots + \frac{S_h(x)}{(x - a_h)^{n_h}}
 + \frac{T_1(x)}{(x^2 + b_1x + c_1)^{m_1}} + \cdots + \frac{T_1(x)}{(x^2 + b_kx + c_k)^{m_k}}.
$$
The final step of the proof is to show that if the degree of $U(x)$ is less than the degree of $(V(x))^p,$ then
$$
\frac{U(x)}{(V(x))^p} = \frac{U_1(x)}{V(x)} + \frac{U_2(x)}{(V(x))^2} + \cdots + \frac{U_p(x)}{(V(x))^p}
$$
where the degree of each $U_i(x)$ is less than the degree of $V(x).$
We can get this result by dividing $U(x)$ by $V(x)$ (the remainder is $U_p(x)$), then dividing the quotient of that division by $V(x)$ again (the remainder is $U_{p-1}(x)$), and so on repeatedly until we get a quotient whose degree is less than that of $V(x),$ which will happen after at most $p-1$ divisions.
That's why, when you have a factor that occurs more than once in the factorization of $D(x)$, you get a term for each power of that factor up to the highest power that divides $D(x).$
