Any sort of matte paint should do and I don't think even the color is THAT critical, I've even had a usable key of a tan wall. There were a lot of shadows that got in the way but a quick trip to PS to generate another mask soon zapped them. Fortunately they were fixed shadows from the props or things would have gotten sticky.
I've used a few options. First, I took a green bed sheet and taped it to the front of my 62" TV (not neccisary to have a TV, mine just happens to take up most of the wall (pinning it to the wall would work fine)).
I actually found that a darker green worked better than a bright green, since the residual green around the edges was less obvious.
I also purchased an 8 x 6 foot piece of thin board (sort of a compressed fiberboard, almost like paneling). This cost me $5.99. I then purchased green paint (any color will work--since you pick the key color with the dropper tool, so long as it is not a color used by your subjects), coated it twice so it is perfectly even, and then put the board landscape or portrait (depending on whether I need a few folks, or someone standing up).
Since the board is so flexible (a pain to get it home, by the way), you can also set it portrait and roll the bottom under your subject's feet (especially if sitting on a stool) to create an "eternal" background without any edges (similar to a photo studio).
I then light the board and the subject with two 500 or 1000 watt halogen lamps (the lights with 5 or 6 foot stands are available at home depot for $39.95 each--they fold up so they're portable, but a little on the bulky side)). I place the lights at full height at a 45 degree angle about 18 feet away from the board and about 10 feet away from the subject (I do this in my family room). Using this approach, I light the subject and the person's shadow does not hit the back board. The lighting is very even and produces an almost perfect key.
I then take the camera and move it as far as possible from the subject (our kitchen is opposite our family room so I have extra room) and then zoom in so the subject is framed with just the green screen showing behind.
At this stage I have to set the white balance (or my halogen's give my subject a slightly different color), plus I MUST set the manual apeture, or my subject ends up too dark (invariably the subject has a white shirt and the camera reduces the brightness with so much light on the subject).
The other advantage of this setup is that there is a counter behind the camera in the kitchen. I set a laptop on the counter (directly behind the camera) and can use it as a teleprompter (several shareware or commercial applications available).
This approach is both cheap and works VERY well. I placed my son as the MC in front of a concert backdrop, put one of the division presidents for GE "in" the company trade show booth, etc. with this proceedure.