Do gravitons interact with each other? I always thought the non-linearity of Einsteins field equations implies that there should be direct graviton-graviton interactions. But I stumbled upon Wikipedia which argues:

If gravitons exist, then, like photons and unlike gluons, gravitons do
  not interact with other particles of their kind. That is, gravitons
  carry the force of gravitation but are not affected by it. This is
  apparent due to gravity being the only thing which escapes from black
  holes, in addition to having an infinite range and traveling in
  straight lines, similarly to electromagnetism.

Is Wikipedia correct? If not, why not? And what then are the arguments that there must be graviton-graviton interactions?

(As of this question being asked, the above paragraph has been removed from Wikipedia.)
 A: I'm pretty sure that you are right and Wikipedia is wrong.  In the linearized gravity approximation at weak curvature, you ignore the gravitational self-back-reaction, but in general gravitons carry energy (as evidenced by the work done by gravitational waves on the LIGO detectors) and therefore contribute to the stress-energy tensor of general relativity, therefore sourcing more gravitons.  Also, some quick Googling finds lots of references to multiple-graviton vertices in effective quantum gravity field theories, whereas the Wikipedia article paragraph you quote has no references.
The issue of how gravitons can "escape" from a black hole without needing to travel faster than light is discussed at How does gravity escape a black hole?.  The short answer is that gravitons can't escape from a black hole, but that's okay because they only carry information about gravitational radiation (which also can't escape from inside a black hole), not about static gravitational fields.
A: So in quantum field theory, the gluon is an operator which changes the color charge of a field.  Since the gluon field itself carries color charge, the gluon-gluon interaction has the same strength as the gluon-quark interaction.
Furthermore, since the QCD coupling constant is $\alpha_S \approx 0.1$, Feynman diagrams with virtual QCD particles in loops contribute with roughly the same strength as one-gluon exchange.  The inability to ignore higher-order corrections is why we call QCD a "non-perturbative" theory.
By contrast, the photon couples to electric charge, but is itself electrically neutral.  Photon-photon vertices therefore don't appear in the Feynman diagrams that describe electromagnetism.
However, photons can interact with virtual particle loops: each photon spends some fraction of its time as a virtual electron-positron pair, and other photons can interact with those virtual charged particles.  This is negligible because the electromagnetic coupling constant, $\alpha_\text{EM} \approx 1/137$, is about ten times feebler than for the strong interaction.
So we can describe electromagnetism quite well, especially at low energy densities, by considering only one-photon exchange between charged particles and ignoring loop corrections, including photon-photon scattering.
Since the gravitational force between the charged fundamental particles is $\sim 10^{40}$ times weaker than the electric force, any perturbation-theoretical approach to gravity will have totally negligible interactions between gravitons, for the same reason that electromagnetism allows you to neglect interactions between photons.  I don't think they're impossible, which seems to be the statement that's bothering you; but I think that they're negligible.
