That is absolutely in the top five most challenging editing tasks. What you do and how you do it depend on: How familiar you are with photoshop tools, what the composition of the image is, and it’s intent (screen/print).
In general, your task is to select the background and delete it. Usually easier said than done. You can try the Extract Filter in version 6 and 7. That may give you a good head start.
Trust me though, this is a daunting task for even the most experienced.
If you uploaded the picture to a web site and told us the link, we might be able to give you a heads up on the best approach, but without seeing the image, well… there’s no magic.
Mask it out would be a better definition. Start by double-clicking the background layer to make it a layer. Add a layer mask and fill/mask out your background. The lassoo, magnetic lassoo, magic wand, brush, pen tool, and extract are many ways of selecting the background so you can fill on your mask. Once it is masked, you can slip the new background layer beneath and flatten it to a tiff or jpeg. As Tony says, what works best on some photos may not be best for others. Hair and complex backgrounds or those too similar to the foreground color are especially daunting.
An other way for with no hassel: After converting to a layer use the Eraser tool than drag it over the other background. Make sure they are the same resolution.