A polynomial satisfies this property if and only if it is a product of prime polynomials of distinct degrees, none raised to a power greater than one except for possibly one linear term raised to a power of degree at most $3$.

As Joe Silverman pointed out, if $Q_i$ are the prime factors of $P$ and $e_i$ are the exponents:

$$
(\mathbb F_2[x]/(P))^* = (\mathbb F_2[x]/(Q_1^{e_1}))^* \times\cdots\times (\mathbb F_2[x]/(Q_r^{e_r}))^*.
$$

As Gerry Myerson points out, these individual factors are cyclic if $e_i=1$. As Gro-Tsen points out, these are not cyclic for greater $e_i$ unless $\deg Q_i = 1$ and $e_i \leq 3$. It is easy to check that they are cyclic, equal to $\mathbb Z/2$ or $\mathbb Z/4$, in the last case. Any group with a non-cyclic subgroup is not cyclic, so we may assume that $e_i=1$ if $\deg Q_i >1$ and $e_i \leq 3$ if $\deg Q_i=1$.

Now we use the well-known lemma:

A product of cyclic groups is cyclic if and only if the orders of the factors are relatively prime.

The "if" follows from the Chinese remainder theorem and the "only if" follows from finding $p^2-1$ elements of order $p$ for a prime dividing the orders of two of the factors.

The order of the factor $Q_i^{e_i}$ is $(2^{ \deg Q_i}-1) 2^{ \deg Q_i (e_i-1)}$. Hence they are relatively prime if and only if at most one of the $e_i$ is $>1$, and also the $2^{\deg Q_i}-1$ are relatively prime. The $2^{\deg Q_i}-1$ are relatively prime exactly when the degrees $\deg Q_i$ are relatively prime, as can be seen by observing that Euclid's algorithm for $2^a-1, 2^b-1$ functions the same as Euclid's algorithm for $a,b$. (This can also be seen by finite field theory - if two finite fields both contain primitive $\ell$th roots of unity for some $\ell$, they both contain the field generated by a primitive $\ell$th root of unity, and hence have a common subfield, and a common factor in their degrees. The converse is also easy.)

Number Theory in Function Fields(2002 / GTM 210). $\endgroup$ – Gro-Tsen May 23 '17 at 22:48