Solution:
Answer: 8

Solution 1. We have $(x+1)^{2}=x^{2}+2x+1 \equiv 2x$, $(x+1)^{4} \equiv (2x)^{2} \equiv -4 \equiv -1$, and $(x+1)^{8} \equiv (-1)^{2}=1$. So the order $n$ divides 8, as $x+1$ and $x^{2}+1$ are relatively prime polynomials modulo 3 (or more conceptually, in $\mathbb{F}_{3}[x]$), but cannot be smaller by our computations of the 2nd and 4th powers.

Solution 2. Here's a solution avoiding the terminology of groups and fields. Let $R(x)=(x+1)^{n}-1-P(x)(x^{2}+1)=3Q(x)$ be the remainder (here $P$ is the quotient), whose coefficients (upon expansion) must all be divisible by 3. Now consider $R(i)$. The coefficients of the even and odd powers of $x$ are divisible by 3, so $R(i)$ must have real and imaginary parts divisible by 3. Notice that $(1+i)^{2}=2i$, $(1+i)^{4}=-4$, $(1+i)^{6}=-8i$, $(1+i)^{8}=16$, and that $(1+i)^{8}-1=15$, which has real and imaginary parts divisible by 3. Since any even power of $(1+i)$ (for $n \leq 6$) yields a purely real or purely imaginary number with a coefficient not divisible by 3, multiplying it by $1+i$ will yield an imaginary part not divisible by 3. To see that $n=8$ works, notice that, when taken modulo 3,
$$\begin{aligned} (x+1)^{8}-1 & = x^{8} + 8x^{7} + 28x^{6} + 56x^{5} + 70x^{4} + 56x^{3} + 28x^{2} + 8x \\ & \equiv x^{8} - x^{7} + x^{6} - x^{5} + x^{4} - x^{3} + x^{2} - x \\ & = (x^{2}+1)(x^{6} - x^{5} + x^{2} - x) \quad (\bmod 3), \end{aligned}$$
as desired.