I am looking for a polynomial of degree $3$ in $\mathbb{F}_{9}$. How do I find one ? And if I have one how do I show that it is irreducible ?
I would start with an irreducible polynomial in $\mathbb{F}_{3}$ like $x^3+2x+1$ Is this procedure correct ?
An then I would use the Rabin test to find out whether $\frac{x^{27}-x}{x^3+2x+1}$ is a division without rest.
Almost there but not quite. You can, indeed, begin by finding a cubic polynomial $p(x)$ that is irreducible over $\Bbb{F}_3$. Adjoining a zero of such a polynomial then automatically generates the field $\Bbb{F}_{27}$. But the intersection $$\Bbb{F}_{27}\cap\Bbb{F}_9=\Bbb{F}_3$$ (in whichever bigger field where you can form that intersection). Therefore $p(x)$ has no zeros in $\Bbb{F}_9$ and, consequently no linear factors in $\Bbb{F}_9[x]$. Being cubic this implies that $p(x)$ automatically remains irreducible over $\Bbb{F}_9$.
The result generalizes as follows. An irreducible polynomial $p(x)$ of degree $n$ in $\Bbb{F}_p[x]$ remains irreducible in $\Bbb{F}_{p^m}[x]$ whenever $\gcd(m,n)=1$. The argument is a bit more delicate, because unlike in the case of cubics irreducibility cannot be deduced from absence of linear factors. But Galois theory comes to the rescue. The condition on gcd implies that the $m$th power of the Frobenius automorphism generates the Galois group $Gal(\Bbb{F}_{p^n}/\Bbb{F}_p)$. Therefore all the zeros of $p(x)$ are conjugate to each other over $\Bbb{F}_{p^m}$ as well.