I use Paint.NET, which is also free (though not open-source, unlike GIMP).
I usually Gaussian Blur the backgrounds slightly, then using the Hue/Sat/Lum adjust tool, I turn the luminosity way down and possibly slightly increase the saturation. In some cases (eg. LPVI Garden background), only certain parts get this treatment - in that example, the fence has been darkened, but the sky has not. Garden's pieces (mostly brown or green) contrast well with the sky's blue color, so it doesn't cause confusion.
One issue, if gradients are desired, you need to make the background as close as possible to the size of the level. In the case of the LPVI Bridge and Garden backgrounds (the Basement background doesn't have this issue), I've created two versions - a ***x160 version for normal height levels, and a ***x320 version for taller levels. (In fact, I even created these alternately-sized versions of the alternate backgrounds, despite that no level actually uses them - all alternate-background levels are no taller than 160px.) The LPIV Wasteland set's mushroom cloud background has no larger version, and thus can only be used on levels 160px tall or less; though Wasteland does have an alternate background that works for any height.