I use Photoshop 6, but The GIMP (
http://www.gimp.org) is also great and very powerful (plus it's free). Some of TGSC's oldest banners on the site were done using Paint Shop Pro 7, I think.
As for how to make them look better, that depends. Highlights and shading are a start, and the layers and layer blendings that Photoshop and The GIMP provide certainly help with that. There's also Hangar-8's "wrinkle sheet" which gives the good wrinkle effect that people use. Just add it to the image and blend it in as an overlay or similar (but keep any iconography above the layer so that it stays crisp and separate)
Anti-aliasing is also a huge help with making banners look like they're not made in MS Paint. Anti-aliasing is where you don't draw in exact pixels, but draw in part pixels as well. If a line is going at 45 degrees then an aliased would just colour in the pixels on the line, which would leave it looking blocky. Anti-aliased lines would colour in the half-covered pixels that the line crosses with 50% of the colour of the line. Using a paintbrush instead of a pencil tool should do that for you.
Another way to get better detail is to do the image at double size and then reduce it down. Double size is probably best as it smooths out any small pixelations but also keeps the detail better than doing it at something like 10-up (where detail a couple of pixels wide would disappear and be lost when it's reduced in size)
Other than that it'd probably depend on the banner and what you're wanting to do.