New methods are introduced for the description and evaluation of tree-level gravitational scattering amplitudes. An N=7 super-symmetric recursion, free from spurious double poles, gives a more efficient method for evaluating MHV amplitudes. The recursion is naturally associated with twistor geometry, and thereby gives a new interpretation for the amplitudes. The recursion leads to new expressions for the MHV amplitudes for six and seven gravitons, simplifying their symmetry properties, and suggesting further generalization. The N=7 recursion is valid for all tree amplitudes, and we illustrate it with a simplified expression for the six-graviton NMHV amplitude. Further new structure emerges when MHV amplitudes are expressed in terms of momentum twistors.