Suppose we have a stream cipher that accepts both a key and an IV.
Let's focus attention on any single output bit of a stream cipher, say z.
Suppose we can express z as a polynomial of the key and IV bits whose
degree is not too large, i.e.,
  z = p(k_0, .., k_127, v_0, .., v_31)
where k_0,..,k_127 are the key bits and v_0,..,v_31 are the bits of
the IV.

In other words, write p() as a sum of terms, where each term is a product
of some set of key/IV bits.  The polynomial p() might have a ridiculous
number of terms (maybe far too many to contemplate writing down) but if
the total degree is not too large, the cube attack is likely to apply.
[Side note: Previously it was believed that as long as the number of
terms is enormous, the cipher is likely safe.  The cube attack shows
that this ain't necessarily so.]

Suppose we know that the total degree of p() is n.  This means that p
is a sum of terms, where every term is a product of at most n variables.
For simplicity I'm going to assume we're working over GF(2), i.e., each
variable represents a boolean value and all polynomials are taken mod 2.

We'll start with a basic lemma about polynomials.  Suppose a(x,y,z)
is a polynomial with three variables, and suppose we can express it in
the form
  a(x,y,z) = b(y,z) x + c(y,z).
Then
  a(1,y,z) - a(0,y,z) = b(y,z).
In other words we have eliminated x from the equation.  When working
in GF(2), we'll never have x^2 or x to any higher power, since x^2 = x,
so the polynomial a(x,y,z) can always be written in this form.  Also
in GF(2), subtraction is the same as addition, so:
  a(1,y,z) + a(0,y,z) = b(y,z).

We can use a similar technique to eliminate multiple variables.
For instance, if
  a(x,y,z) = b(z) yz + c(x,y,z)
where c(x,y,z) is a polynomial that does not contain any terms that
are a multiple of yz, then
  a(1,1,z) + a(1,0,z) + a(0,1,z) + a(0,0,z) = b(z).
Notice how the points (1,1), (1,0), (0,1), (0,0) can be viewed as
the corners of a square in 2 dimensions.  The same can be generalized
to any number of variables.  For instance, with 3 variables, we'll
evaluate at 8 points, corresponding to the corners of a cube in 3
dimensions -- hence the name cube attack.

So now let's return to our stream cipher.  Suppose we can express
the polynomial p() in the form, say,
  p(k_0, .., k_127, v_0, .., v_31)
    = l(k_0, .., k_127) v_0 v_1 v_2
      + q(k_0, .., k_127, v_0, .., v_31)
where l(k_0, .., k_127) is a linear sum of key bits, v_0 v_1 v_2
is a product of some subset of IV bits, and q() is any polynomial that
does not contain any terms that are a multiple of v_0 v_1 v_2.
If we can express p() in this form, then we can eliminate variables
to find
  p(..., 0,0,0, ...) + p(..., 0,0,1, ...) + p(..., 0,1,0, ...)
    + p(..., 0,1,1, ...) + p(..., 1,0,0, ...) + p(..., 1,0,1, ...)
    + p(..., 1,1,0, ...) + p(..., 1,1,1, ...)
  = l(k_0, .., k_127).
Here we have plugged in all 2^3 possible combinations of values
for v_0,v_1,v_2 into p().  After summing these 8 outputs from p(),
the result can be expressed as a linear combination of key bits.

Notice what this means for the stream cipher.  If we can get the
keystream corresponding to 8 different IVs, where v_0,v_1,v_2 vary
over all 2^3 possible combinations and the remaining key bits remain
fixed, then this corresponds to learning the value of p() after
evaluating p() on these 8 inputs.  By the above reasoning, if we
sum these 8 known outputs from p(), we get l(k_0, .., k_127): a
known linear combination of key bits.  So this leaks a linear function
of the key bits.

If we can find 128 of these leakages, then this leaks 128 linear
functions of the unknown key bits, so we can set up 128 linear
equations with 128 unknowns and solve for the key.  This gives a
key-recovery attack.

Of course there is nothing special about v_0,v_1,v_2 in the above.
We can replace the term v_0 v_1 v_2 with any term that can be written
as a product of a subset of IV bits (and only IV bits).  If the total
degree of the polynomial is n, and if the terms of p are reasonably
random, then heuristically we'd expect to succeed by looking at terms
that are a product of n-1 IV bits.

The rest of the attack Adi described consists of clever ways for
figuring out how to express p() in this form, how to make the attack
work with only black-box access to the stream cipher, and various
other clever improvements.  He also showed how to break a stream
cipher that seems plausibly immune to all other attacks previously known:
in his talk, he described a hypothetical stream cipher that seemed
ridiculously hard to break by all known methods (he just piled on one
security feature after another until he got a design where I just had
to laugh -- since it seemed ridiculous to imagine an attack on the
design, yet I knew if he was describing this cipher he had to have
some trick up his sleeve to break it), and then showed how to break
it with a cube attack.  Wow!