Factorisation of polynomials over finite fields can be solved in probable polynomial time with a randomised algorithm (which is much easier than factorisation of integers). For a fixed ground field such as $\mathbb F_2$, this can be made deterministic. Naturally this allows irreducibility testing in similar time.
If we're just interested in the yes/no irreducibility test, there are some small savings and the algorithm as follows. Note that we can compute $X^{2^k}-X\mod{f(X)}$ with $k$ repeated squarings and a subtraction and so computing $\mathrm{GCD}(X^{2^k}-X,f(X))$ can be done in time polynomial in $k$ and the degree of $f(X)$.
Step 1. We compute $\mathrm{GCD}(X^{2^d}-X,f(X))$ where $d=\mathrm{deg}f$. If this is not $f(X)$ then $f$ is not irreducible as it either has repeated roots or roots outside $\mathbb F_{2^d}$. If it is $f(X)$ we proceed to step 2.
Step 2. For each prime $p|d$ we let $d'=d/p$ and compute $\mathrm{GCD}(X^{2^{d'}}-X,f(X))$. If this is not 1 then $f(X)$ has a root in the subfield $\mathbb F_{2^{d'}}$ and $f(X)$ is not irreducible.
If step 2 passes for all $p|d$ then all of the roots lie in $\mathbb F_{2^d}$, but not in a subfield so that $f(X)$ is irreducible.
