Field with $125$ elements
If a cubic polynomial of $\mathbb{F}_5[x]$ is reducible, then it splits into a linear factor and a quadratic factor or into the product of three linear factors. Linear factors are very easy to test for, as $(x-a)$ is a factor of $f$ if and only if $f(a) = 0$.
So you might choose a random degree $3$ polynomial and test for the five possible roots.
For instance, I'm tempted to try $f(x) = x^3 + 2x + 1$. Then $$\begin{align} &f(0) = 1, \\ &f(1) = 4, \\ &f(2) = 8 + 4 + 1 \equiv 3, \\ &f(3) = 27 + 6 + 1 \equiv 4, \\ &f(4) = 64 + 8 + 1 \equiv 3. \end{align}$$
As none of these are zero, $f(x)$ is an irreducible cubic.
Note that testing for roots explicitly doesn't work for higher degree polynomials. It is possible that a reducible quartic factors into the product of two quadratics. So though there are no roots, it might still be reducible. However since we know that a reducible cubic has a linear factor, we can test just for the linear factor.
The method given by mixedmath is correct. In the illustration the random polynomial selected turned out to be irreducible. In general you may have to try many random ones before becoming lucky.
Instead of trying something wildly random restrict to those satisfying Eisenstein criterion. (because something that is reducible over integers is not going to help us). As we are working mod 5 let us try prime coefficients less than 5.
Trial 1: $x^3+2x+2$. This polynomial evaluates to zero at 1.
Trial 2: Now let us try $g(x)=x^3+3x+3$. Now $g(0) =1$ $$ g(1)=2$$ $$g(2)=2$$ $$g(3)=4$$ $$g(4)=1$$ So using the same reasoning of mixedmath we arrive at an irreducible polynomial.
@mixedmath @P Vanchinathan
One can generate a field with 125 elements by taking the powers $M^n$ of a certain $3 \times 3$ matrix $M$ with coefficients in $\mathbb{F}_5$ of order 124.
Edit: In order to be explicit, let us consider matrix
$$M = \begin{pmatrix}0&0&1\\2&0&0\\0&1&1 \end{pmatrix}$$
Cayley Hamilton theorem applied to $M$ gives: $M^3=2I_3+M^2 \ \ (1)$.
Let $R$ be the ring of $3 \times 3$ matrices with coefficients in $\mathbb{F}_5$ (with ordinary addition and multiplication of matrices).
The subset $S$ of matrices of the form $aI_3+bM+cM^2$ (for any $a,b,c \in \mathbb{F}_5$) is a subring of $R$ (by application of (1) for the stability by multiplication).
The represention of an element of $S$ under the form $aI+bM+cM^2$ is unique. Otherwise, an identity of the form $aI+bM+cM^2=a'I+b'M+c'M^2$ (where $(a,b,c) \neq (a',b',c')$) would infer the existence a polynomial of degree at most 2 that annihilates matrix $M$, and one can verify that no such "minimal" polynomial exist.
As a consequence $S$ is in bijective correspondance with $\mathbb{F}_5^3$, thus has $5 \times 5 \times 5 = 125 $ elements.
Let us now consider set $S'$ defined as the set of all powers $M^n$ which are clearly elements of $S$ by using iteratively (1)).
In fact $S=S'\cup \{0\}$ (where 0 is the null matrix).
Indeed, on one hand $S'$ is included in $S$ because, by successive applications of (1), one can lower any polynomial in $M$ into an at most degree 2 polynomial. And, on the other hand, one can verify that $M$ has order 124 (it can certainly be be proved using the correspondence between matrices and - irreducible - polynomial through the concept of companion matrix).
Thus $S$=$S'$ minus ${0}$ is a (cyclic) group for multiplication.
Therefore $S$ is a field with 125 elements.
(all this in accordance with the fact that a finite field is commutative, and has a cyclic multiplicative group).
See this reference;