Showing $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$

As you note, $\gcd(n^3+1,n^2+2) = \gcd(1-2n,n^2+2)$.

Now, continuing in that manner, $$\begin{align*} \gcd(1-2n, n^2+2) &= \gcd(2n-1,n^2+2)\\ &= \gcd(2n-1, n^2+2+2n-1)\\ &= \gcd(2n-1,n^2+2n+1)\\ &= \gcd(2n-1,(n+1)^2). \end{align*}$$

Consider now $\gcd(2n-1,n+1)$. We have: $$\begin{align*} \gcd(2n-1,n+1) &= \gcd(n-2,n+1) \\ &= \gcd(n-2,n+1-(n-2))\\ &=\gcd(n-2,3)\\ &= 1\text{ or }3. \end{align*}$$ Therefore, the gcd of $2n-1$ and $(n+1)^2$ is either $1$, $3$, or $9$. Hence the same is true of the original gcd.

Playing around along the lines you were exploring should work. Let's do it somewhat casually, aiming always to reduce the maximum power of $n$.

If $m$ divides both $n^3+1$ and $n^2+2$, then $m$ divides $n(n^2+2)-(n^3+1)$, so it divides $2n-1$. (You got there.)

But if $m$ divides $n^2+2$ and $2n-1$, then $m$ divides $2(n^2+2)-n(2n-1)$, so it divides $n+4$. (This move is slightly risky. In some cases this kind of move could introduce spurious common divisors. But (i) In this case it doesn't; and (ii) We will be checking at the end anyway whether our list of candidates is correct.)

But if $m$ divides $n+4$ and $2n-1$, then $m$ divides $2(n+4)-(2n-1)$, so it divides $9$.

We did not work explicitly with greatest common divisors, so we are not finished. We must show that $1$, $3$ and $9$ are all achievable. For $\gcd$ $1$, let $n=0$. For $\gcd$ $3$, let $n=2$. For $\gcd$ $9$, let $n=4$.

I'm carrying out a congruence procedure, so that you have different approaches.

If $p \, | \, n^3 + 1$ and $p \, | \, n^2 + 2$, then $2n \equiv 1 \pmod p$, which means $$ -8 \equiv 8n^3 = (2n)^3 \equiv 1^3 \equiv 1 \pmod p, $$ hence $9 \equiv 0 \pmod p$ and assuming $p$ is a prime means $p = 3$. This means the $\gcd$ is a power of $3$. Now I'm checking powers of $3$ by hand using congruences.

EDIT : As miracle's comment says, I got far too carried away by liking primes so much : a good way to say that this proof is done is that $9 \equiv 0 \mod p$ means $p \, | \, 9$, hence getting examples is enough to get our answer.

If $n \equiv 0 \pmod 3$, this $\gcd$ is clearly $1$.

If $n \equiv 1 \pmod 3$, $n^3 + 1 \equiv 1 \pmod 3$ so that the $\gcd$ is again $1$.

If $n \equiv 2 \pmod 3$, then $9 \, | \, n^3 + 1$ and $3 \, | \, n^2 + 2$. But letting $n = 3k+2$ we notice that \begin{align*} (3k+2)^3 + 1 & = (3k)^3 + 3 \cdot (3k)^2 \cdot 2 + 3 \cdot 3k \cdot 2^2 + 2^3 +1 \\& \equiv 9(k+1)\pmod{27} \end{align*} which is $0$ if and only if $k \equiv 2 \pmod 3$. Carry on! We get $$ (3k+2)^2 + 2 \equiv (3k)^2 + 2 \cdot (3k) \cdot 2 + 2^2 + 2 = 9k^2 + 12k + 6 \equiv 0 \pmod{27} $$ if and only if $$ 3k^2 + 4k + 2 \equiv 0 \pmod 9 $$ but reading this $\bmod 3$, we get $k \equiv 1 \pmod 3$, a contradiction.

I must say it is a little longer than the $\gcd$ proof : I expected people to put up to $\gcd$ proof, so I've shown this one instead. I like those proofs because they're mechanical ; I didn't have to think much to write it, I just chose to go this way and things always go as expected (assuming the question asks something that's true, obviously)... Now I've only proven that the $\gcd$ divides $9$ : again, to show that the $3$ possibilities actually happen, pull off examples like Andre Nicolas.

Hope that helps,