At the risk of sounding pompous, here's a few comments from the Guru.

The bottom line is that your background (green or blue screen) should be evenly lit and coloured since what you're going to tell your computer to do is... "take all the pixels with this particular green value and replace it with something else."
If the greenscreen has different values then your computer will ignore the bits which are the "wrong" green and you don't get a clean key. You can tell your computer not to be so fussy and to accept a large range of greens but then you run the risk that it removes bits of the subjects which you wanted to keep.

A few trade secrets here: The biggest problem is "fringing" or getting a fuzzy line between the subject and the green, this is nearly always caused by light being reflected from the background onto the subject. You'll often hear recommendations to use red,orange or other coloured backlights to cure this, all rubbish, adding light won't always cure the problem, you've got to stop green( or blue, depending on what you're keying out) falling on your subject. Most of the time just moving your subject away from the background cures the problem.

Another urban myth is that, if anything, the background has to be too bright. Wrong. An over-bright background is harder to key than a slightly underlit one since the colours tend to desaturate by overexposure, making it harder for the computer to "find" the right green.

If you're greenscreening then (and may I smack my own bottom for admitting this) cheap fluorescent tubes are a good way to create soft, even lighting on a budget, providing you're not going to muck about with shutter speeds or suchlike.

A quick and dirty way to check that your background is evenly lit is to use the zebra or overexposure warning on your camcorder. Just point the camcorder at the screen and start to manually open the aperture, the "zebras" will appear in any hotspots. Keep opening the aperture and the last areas to "go zebra" will be the cool spots. If this talk about "zebras" makes no sense to you, don't worry, just looking at the screen with half-closed eyes can give you a clue as to which bits are "hot" and which need a bit more oomph.