It is known that a polynomial with degree less than $4$ is irreducible if and only if it has no roots. Suppose we have the following cubic polynomial, $ax^3+bx^2+cx+d=0$ with $a \neq 0$ and $a,b,c,d \in \mathbb{Z}_{5}$. $a$ therefore can take 4 elements and $b,c,d$ can take $5$ elements and our total number of polynomials is thus $500$. Now, we need to narrow down the irreducible polynomial.
Where do I go from here?
You can divide it by $a$, thereby getting a polynomial of the type $x^3+b'x^2+c'x+d'$. And, of course, you cannot take $d'=0$. So, now you only have $100$ cases to consider.
Actually, you can suppose that $b'=0$, using the same trick that works for solving cubic equations over $\mathbb C$ ($x\rightarrow x-\frac{b'}3$). So, now you only have $20$ possibilities. That's not a lot.
By the way, $x^3+x+1$ will do.