How to know that $a^3+b^3 = (a+b)(a^2-ab+b^2)$

If you want to know if $a^n + b^n$ is divisible by $a+b$ (or by $a-b$, perhaps), you can always try long division, whether explicitly or in your head. I can't figure out a way to do the LaTeX or ASCII art for it here to do it explicitly, so I'll show you how one would do it "in one's head".

For example, for $a^3+b^3$, to divide $a^3+b^3$ by $a+b$, start by writing $a^3+b^3= (a+b)(\cdots)$. Then: we need to multiply $a$ by $a^2$ to get the $a^3$, so we will get $a^3+b^3=(a+b)(a^2+\cdots)$. The $a^2$ makes an unwanted $a^2b$ when multiplied by $b$, so we need ot get rid of it; how? We multiply $a$ by $-ab$. So now we have $$a^3+b^3 = (a+b)(a^2-ab+\cdots).$$ But now you have an unwanted $-ab^2$ you get when you multiply $b$ by $-ab$; to get rid of that $-ab^2$, you have to "create" an $ab^2$. How? We multiply $a$ by $b^2$. So now we have: $$a^3 + b^3 = (a+b)(a^2-ab+b^2+\cdots)$$ and then we notice that it comes out exactly, since we do want the $b^3$ that wee get when we multiply $b^2$ by $b$; so $$a^3 + b^3 = (a+b)(a^2-ab+b^2).$$

If the expression you want is not divisible by what you are trying, you'll run into problems which require a "remainder". For instance, if you tried to do the same thing with $a^4+b^4$, you would start with $a^4+b^4 = (a+b)(a^3+\cdots)$; then to get rid of the extra $a^3b$, we subtract $a^2b$: $a^4+b^4 = (a+b)(a^3 - a^2b+\cdots)$. Now, to get rid of the unwanted $-a^2b^2$, we add $ab^2$, to get $a^4+b^4 = (a+b)(a^3-a^2b+ab^2+\cdots)$. Now, to get rid of the unwanted $ab^3$, we subtract $b^3$, to get $$a^4+b^4 = (a+b)(a^3-a^2b+ab^2 - b^3+\cdots).$$ At this point we notice that we get an unwanted $-b^4$ (unwanted because we want $+b^4$, not $-b^4$). There is no way to get rid of it with the $a$, so this will be a "remainder". We need to cancel it out (by adding $b^4$) and then add what is still missing (another $b^4$), so $$a^4 + b^4 = (a+b)(a^3-a^2b+ab^2 -b^3) + 2b^4.$$ (Which, by the way, tells you that $a^4-b^4 = (a+b)(a^3-a^2b+ab^2-b^3)$, by moving the $2b^4$ to the left hand side).

Keeping $a$ fixed and treating $a^3 + b^3$ as a polynomial in $b$, you should immediately notice that $-a$ will be a root of that polynomial. This tells you that you can divide it by $a + b$. Then you apply long division as mentioned in one of the comments to get the other factor.

It's a homogenization of the cyclotomic factorization $\rm\ x^3 + 1 = (x+1)\ (x^2 - x + 1)\:.\ $ Recall that the homogenization of a degree $\rm\:n\:$ polynomial $\rm\ f(x)\ $ is the polynomial $\rm\ y^n\ f(x/y)\:.\ $ This maps $\rm\ x^{k}\ \to\ x^{k}\ y^{n-k}\ $ so the result is a homogeneous polynomial of degree $\rm\:n\:.\ $ While this cyclotomic factorization is rather trivial, other cyclotomic homogenizations can be far less trivial. For example, Aurifeuille, Le Lasseur and Lucas discovered so-called Aurifeuillian factorizations of cyclotomic polynomials $\rm\;\Phi_n(x) = C_n(x)^2 - n\ x\ D_n(x)^2\;$. These play a role in factoring numbers of the form $\rm\; b^n \pm 1\:$, cf. the Cunningham Project. Below are some simple examples of such factorizations:

$$\begin{array}{rl} x^4 + 2^2 \quad=& (x^2 + 2x + 2)\;(x^2 - 2x + 2) \\\\ \frac{x^6 + 3^2}{x^2 + 3} \quad=& (x^2 + 3x + 3)\;(x^2 - 3x + 3) \\\\ \frac{x^{10} - 5^5}{x^2 - 5} \quad=& (x^4 + 5x^3 + 15x^2 + 25x + 25)\;(x^4 - 5x^3 + 15x^2 - 25x + 25) \\\\ \frac{x^{12} + 6^6}{x^4 + 36} \quad=& (x^4 + 6x^3 + 18x^2 + 36x + 36)\;(x^4 - 6x^3 + 18x^2 - 36x + 36) \\\\ \end{array}$$