The main explanation of the fourth step of the first algorithm in the link you gave is given in the proof. In order to construct an extension of degree $p^a n$, you first construct an extension $\def\FF{\mathbb{F}}\FF(\beta)/\FF$ of degree $n$, another extension $\FF(\alpha_a)/\FF$ of degree $p^a$, and then the field $\FF(\alpha_a, \beta)/\FF$ has to be degree $p^a n$.
A common trick to find generators for a field extension with multiple generators is to take linear combinations. By looking at the action of the Galois group, it's easy to see that $\alpha_a + \beta$ has full order. Use your favorite method to find its minimal polynomial.
To construct the extension of degree $p^a$, they constructed it in stages, with extensions $\FF(\alpha_k)/\FF$ of degree $p^k$. Artin-Schreier theory says that (in characteristic $p$), any Galois extension of degree $p$ (all finite finite field extensions are Galois) can be written as the splitting field of $x^p - x - r$ for some $r$. Lemma 5 gives a way to find suitable $r$.
For the record, I don't follow exactly what their formulas are doing either. But by knowing what they're trying to do, IMO it's easy enough to come up with your own way to do it.
There are two crucial results here.
Dedekind's theorem: Let $f$ be a monic irreducible polynomial over $\mathbb{Z}$ of degree $n$ and let $p$ be a prime such that $f$ has distinct roots $\bmod p$ (this is true for precisely the primes not dividing the discriminant). Suppose that the prime factorization of $f \bmod p$ is
$$f \equiv \prod_{i=1}^k f_i \bmod p.$$
Then the Galois group $G$ of $f$ contains an element of cycle type $(\deg f_1, \deg f_2, ...)$. In particular, if $f$ is irreducible $\bmod p$, then $G$ contains an $n$-cycle.
Frobenius density theorem: The density of the primes with respect to which the factorization of $f \bmod p$ has the above form is equal to the density of elements of $G$ with the corresponding cycle type. In particular, for every cycle type there is at least one such prime $p$.
It follows that
$f$ is reducible $\bmod p$ for all $p$ if and only if $G$ does not contain an $n$-cycle.
The smallest value of $n$ for which this is possible is $n = 4$, where the Galois group $V_4 \cong C_2 \times C_2$ has no $4$-cycle. Thus to write down a family of examples it suffices to write down a family of irreducible quartics with Galois group $V_4$. As discussed for example in this math.SE question, if
$$f(x) = (x^2 - a)^2 - b$$
is irreducible and $a^2 - b$ is a square, then $f$ has Galois group $V_4$. In particular, taking $b = a^2 - 1$ the problem reduces to finding infinitely many $a$ such that
$$f(x) = x^4 - 2ax^2 + 1$$
is irreducible. We get your examples by setting $a = 0, 5$.
By the rational root theorem, the only possible rational roots of $f$ are $\pm 1$, so by taking $a \neq 1$ we already guarantee that $f$ has no rational roots. If $f$ splits into two quadratic factors, then they both have constant term $\pm 1$, so we can write
$$x^4 - 2ax + 1 = (x^2 - bx \pm 1)(x^2 + bx \pm 1)$$
for some $b$. This gives
$$2a = b^2 \mp 2.$$
Thus $f$ is irreducible if and only if $2a$ cannot be written in the above form (and also $a \neq 1$).
Classifying polynomials $f$ with this property seems quite difficult in general. When $n = 4$, it turns out that $V_4$ is in fact the only transitive subgroup of $S_4$ not containing a $4$-cycle, but for higher values of $n$ there should be lots more, and then one has to tell whether a polynomial has one of these as a Galois group...
(Except if $n = q$ is prime; in this case $q | |G|$ so it must have a $q$-cycle.)
Best Answer
Using the Berlekamp Algorithm we obtain $$ x^7-1=(x^3 + x^2 + 1)(x^3 + x + 1)(x + 1). $$ The factorization is unique, up to permutations and units, because the polynomial ring $\Bbb{F_2}[x]$ is a UFD.