To do it yourself properly would require a knowledge of green screen technology. If you don't do it properly, meaning having the proper equipment and basic video skills including understanding how to correctly light a subject, it will look cheesy.
There are companies out there that will do it right for a relatively small amount of money.
This kind of thing can do far more harm than good if not done properly, I strongly suggest taking the high road here and get the client to pay for a service like this. Have them look at the demo presentation, they'll most likely be blown away and get out the checkbook. :-)
If you want to take a stab at this and see what you'll be getting into you really only need a video camera. Generally you use special colored paint either blue or green for background. I believe the RGB values for green as an example would be R0 G255 B0 . It easy to key out a color like that.
You don't absolutely need the blue or green though as any decent editor will be able to key out any solid color. Find yourself a solid color wall, make sure your subject is not wearing anything similar in color to the wall or they are going to disappear too. The imporatant thing here is to eliminate shadows on the wall so you need a lot light on it and diffused light on your subject.
Once you get a video taped for starters you can use Ulead Video Studio for editing, they have a free trial. That's about the cheapest program I'm aware of with the ability to do green screen. Once you bring the footage into the program you'll have an option somewhere to selct the color you want to key out of the video... no more back ground color.