Art Programs
Big Note: It is mostly-possible to make wesnoth graphics with nothing more than MSPaint or Appleworks. However, there are two major and vital things lacking in those programs - first, these programs cannot make images with transparent pixels, and second, they may not be able to save in the PNG format used by Wesnoth. A program capable of those will have to be applied to images made with MSPaint when they are finished.
Free Image Editors
The following are free image editing programs which can be used to create graphics for wesnoth. These programs are Open-Source Software, like wesnoth, meaning they are free to use, and that you are free to look at the sourcecode.
The GIMP (for windows & linux); the "Gnu Image Manipulation Program" is recommended.
Seashore (for mac) this port of the the GIMP to a cocoa-based gui is recommended. Seashore provides the basic features of GIMP.
Pixen (for mac) is the OpenSword Group's tool for traditional SNES style sprite art - unlike most other editors, it has been designed for that specific task, and users may find it much less daunting than the Gimp or Photoshop. This program was written in cocoa, and has a very good interface - version 3 will even include built-in support for making animations.
JDraw (for anything that can run Java - mac and windows included) is an image editor which has a subset of the features of Pixen, and a superset of the features of MSPaint. It is a simple, straightforward pixel editing program. If you use a mac, Pixen is probably a better idea.
Paint.net (for windows) is generally regarded as inferior to the Gimp or Photoshop, but some might find it of interest.
Allegro Sprite Editor (for windows/linux) is a sprite editing program. Free/OSS, note that it is NOT capable of saving PNGs.
Free Image Post-Processors
PNGCrusher (for mac) is a handy lightweight tool that will compress your PNGs much more efficiently than Photoshop. It is best used in tandem with saving the files from GraphicConverter, with the PNG filtering options on. The tool it is based on, OptiPNG, is open source, and runs on both linux and windows.
Proprietary Image Editors
GraphicConverter (for mac) by Lemkesoft is an excellent program for preparing and compressing png images for the game, and may also be useful for the creation of images. The shareware fee is $30, although large parts of the program are fully functional for free.
Pixel Image Editor (for mac/windows/linux/BeOS/others) is a very full-featured program, intended to fulfill the same function that photoshop does. It currently has a shareware fee of $32, though the final price once the product reaches v2.0, will be $79.
JTL Ultimate Paint (for windows) is a basic painting program, following the tradition of the earlier "DeluxePaint". Geared at painting, it can use photoshop plugins. It currently costs $34 for a basic version. I do not know if this program can export PNG images, so caveat emptor.
Pro Motion (for windows) is a commercial pixel editing program. It has many features tailored for animation and seamless square-tile creation, as well as features designed to ease the creation of images that would run in a game on the Game Boy Advance or a Mobile Phone platform. The price of the normal version is $78.
GraphicsGale (for windows) is a pixel editing program designed for animation. It has both a freeware version, and a 1995¥ (roughly $20) shareware version. Be warned that it can not save files in the PNG format.
Photoshop or Photoshop Elements (for windows & mac), these industry standard Adobe applications are available for ~$700 and ~$100, respectively (the prices vary depending on where you get them). If you can acquire the use of these programs through a business or academic situation, they are extremely powerful, and are more than capable of some very advanced sprite techniques which elude simple bitmap programs - the price, however, is likely too much of a barrier to entry for most contributors. Photoshop should have little advantage over Elements for creating unit and terrain art. Photoshop (and presumably Elements) does not compactly save PNG files. For space savings, Adobe users are recommended to resave final PNGs through Adobe's companion application ImageReady, or another application such as GraphicConverter or PNGCrusher. Note - the ImageReady compression can also be used by saving the files through the "Save for Web..." menu command within Photoshop, if ImageReady is installed.