Suppose $f=x_0x_2(x_1+1)+x_1x_3(x_0+1)$, annihilator is such function $g$, so that $gf=0$ for all $x$
Intuitively solution(for some reason) is obvious - $g=x_0x_1$, which holds true. (Cloud sagemath online script)
It bugs me, that I can't explain this "intuitively". How to arrive at solution properly, not guessing?
PS: We can skip trivial solution $g=0$, function $g$ should depend on $x_n$ variables, at least some of them. Of course $\mathbb{F}_2$ is meant here.
I'm not sure if I really believe that this is of any use at attacking a stream cipher, but I'll answer your question anyways.
What $gf = 0$ means is that, for any input $x$, we have either $f=0$ or $g=0$.
Now, in the case of $g = x_0x_1$, then this $g$ will be 0 unless $x_0 = x_1 = 1$.
In that case, the first term of $f$, namely $x_0x_2(x_1+1)$ will be 0 (as $x_1+1 = 1+1 = 0$). And, the second term of $f$, namely $x_1x_3(x_0+1)$ will be 0 (as $x_0+1 = 1+1 = 0$).
Hence, whenever $g \ne 0$, we have $f=0$, and so $gf = 0$.
This observation gives a fairly obvious way to create a nontrivial annihilator of any function $f$ (other than $f=1$ for all inputs); namely:
Find a set of inputs that give $f=0$ (technically, this is an NP-hard problem (!), but in practice is fairly easy).
Create a $g$ that is 1 for that specific input, and 0 otherwise.
For example, if $f=0$ for $x_0 = 0, x_1 = 1, x_2 = 0$, then this annihilator would be $g = (x_0 + 1)x_1(x_2 + 1)$
