Light the green background evenly and brightly but don't overexpose it
Your best bet to get the correct exposure is to run a few tests in a methodological fashion.
If you can't afford to run tests then light the green screen at about 1 stop over key (i.e. light your greenscreen to reflect twice as much light as your foreground elements and then set your camera's exposure to comfortably capture the foreground elements).
Try to avoid using filters on the lens. Diffusion can make the key very hard to pull. (And make sure the lens is clean!)
Avoid throwing shadows on the green screen
Try to limit the amount of reflected green light bouncing from the screen onto the actors (this can be achieved by careful lighting; by moving the foreground elements as far away from the green screen as possible or by simply covering unused sections of the green screen in black)
Avoid using the same colour in the actor's clothes as in the green screen.
One way to check that your exposure is about correct is to place a bit of white card under the key light and then view the scene through a green filter. The white card should "disappear" against the green screen.
Hair, especially if it's moving (e.g. having an actor's/actress' long hair blowing in the wind against a green screen will be a nightmare to work with)
No, you can use any colour screen you wish. Any compositing software worth its place in this world will be able to chroma-key any colour. Blue and Green are often chosen because the human skin contains very little blue or green pigment. Green screens are often used for shoots outside as sunlight can register on a camera as "blue" causing problems when chroma keying.
Set the camera to a gain of 0db (this gives the best signal to noise ratio and the widest dynamic range)
Use a video camera with the least chroma subsampling (i.e. 4:4:4 is best). It is possible to get minimally acceptable results from DV (4:1:1) or HDV (4:2:0) but your life will be easier (and the resulting key considerably better) if you use a higher quality capture medium. Since keying relies on color information that is disregarded as part of any color space reduction from 4:4:4, all lossy compression formats will result in decreased edge detail.