Warren- I've modified the previous answer, which mixed up the type of evidence needed to demonstrate gravity waves with the type needed to demonstrate their quantized version (gravitons). Although we thought we had cleared out all the mistaken answers from earlier versions, another one crops up every now and then.
On to your question: It's not either/or. GR implies
the existence of gravity waves. The slowing down of binary pulsars provides strong evidence for their existence. Experiments (LIGO and VIRGO) are running which may find more direct evidence.
Gravitons would be the quantum version of these gravity waves, just as photons are the quantum version of electromagnetic waves. The existence of photons makes no problems for the classical EM theory of say radio waves under ordinary circumstances. The existence of gravitons would, unfortunately, pose no problem for the GR theory of gravity waves under any circumstances we can hope to observe. So that means we'll probably never find direct evidence of gravitons.
We nevertheless believe that gravitons will be present in any quantum theory of gravity, since all other large-scale waves are quantized. In fact, any non-quantized waves would lead to severe logical problems, since they would provide a way to unravel the uncertainty relations, which are a direct implication of the quantum formalism.
(published on 09/30/12)