This is a problem from Artin's Algebra.
According to Mathematica the factorization is
$$x^7 + x + 1 = (x + 4)(x^2 + x + 3)(x^2 + x + 4)(x^2 + x + 6)$$
Is there some clever trick to avoid doing this by trial and error? It's not that hard to see that 3 is a root, but I don't see how to find the quadratic factors.
Consider what elements $\alpha \in \mathbb{F}_{7^k}$ could possibly be a root, other than $3$. Since $x \mapsto x^7$ is the Frobenius map, if $\alpha$ has minimal polynomial $f(x)$ then $\alpha^7$ must also be a root of $f(x)$. But we have $\alpha^7 = - \alpha - 1$ by assumption, so $f(x)$ must be divisible by
$$(x - \alpha)(x + \alpha + 1) = x^2 + x - (\alpha^2 + \alpha).$$
Conversely, any irreducible polynomial of the form $x^2 + x + a \in \mathbb{F}_7[x]$ must be a factor, because it must have a root with the above property. This reduces the problem to figuring out when $x^2 + x + a$ is irreducible. The discriminant here is $\sqrt{1 - 4a}$ which lies in $\mathbb{F}_7$ iff $1 - 4a = 0, 1, 2, 4$, hence iff $a = 2, 0, 5, 1$. So $x^2 + x + a$ is irreducible iff $a = 3, 4, 6$, which must be precisely the three irreducible quadratic factors.