I've made backgrounds for a few of my cels in 
the past... mostly, when i make them I just take 
a screencap of my cel for reference, and try to 
accomplish something close with simple 
watercolors on posterboard/heavy weight paper.

I suppose if you wanted to try doing something 
completely digital with just take a screencap, 
and smudging the character out... i would think 
Adobe Photoshop would be a good program for 
doing so. 

Though, most of the people I know that make 
their own backgrounds, actually paint them.

~yaten