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 (Windows, Linux & Mac OS X); the "Gnu Image Manipulation Program" is recommended.
Seashore (Mac OS X) this port of the the GIMP to a cocoa-based gui is recommended. Seashore provides the basic features of GIMP.
Pixen (Mac OS X) 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 (Windows) is generally regarded as inferior to the Gimp or Photoshop, but is easier to look at for those with shorter attention spans, so some might find it of interest.
Allegro Sprite Editor (Windows and Linux) is a sprite editing program. Free/OSS, note that it is NOT capable of saving PNGs.
Paintbrush (Mac OS X) is a program intended to be a slightly modernized clone of the old MacPaint/MSPaint. Free/OSS, but note that though it is capable of saving PNGs, it is not capable of handling transparency.
Free Image Post-Processors
PNGCrusher (Mac OS X) 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.
ImageOptim (Mac OS X) optimizes images so they take up less disk space and load faster. It provides GUI for various optimisation tools: AdvPNG from AdvanceCOMP, OptiPNG, Pngcrush, JpegOptim, jpegtran from libjpeg, Gifsicle and optionally PNGOUT.
Proprietary Image Editors
GraphicConverter (Mac OS X) 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 (Mac OS X, Windows, Linux, BeOS, and 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 (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 (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 (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 (Windows and Mac OS X), these industry standard Adobe applications are available for approximately USD $100 and $700, respectively, depending on what version of the software you purchase and where you purchase it. You may be able acquire the use of these programs through a business or academic situation. Adobe Photoshop is extremely powerful, and is more than capable of some very advanced sprite techniques which elude simple bitmap programs - the price, however, can be a barrier to entry for some contributors. More advanced (and therefore more expensive) version of Photoshop should have little advantage over Elements (the entry-level version, usually available for approximately USD $100) 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.