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. Works on Linux/Windows/MacOsX.
Aseprite is animated sprite editor & pixel art tool. Present in Linux packages (Debian/Ubuntu) and available in source on GitHub, but Windows/MacOsX binary is sold on home page.
mtPaint intented to easily create pixel art and manipulate digital photos. Works on Linux/Windows.
GrafX2 is a bitmap paint program inspired by the Amiga programs Deluxe Paint and Brilliance. Specialized in 256-color drawing, it includes a very large number of tools and effects that make it particularly suitable for pixel art, game graphics, and generally any detailed graphics painted with a mouse. The program is mostly developed on Linux and Windows, but is also portable on many other platforms.
Pencil2D lets you create traditional hand-drawn animation (cartoon) using both bitmap and vector graphics. Works on Linux/Windows/MacOsX.
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.
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
The utils/woptipng.py script is included in Wesnoth's source code. It runs the tools from ImageMagick/GraphicsMagick, OptiPNG and Advdef; links to all of these are below.
ImageMagick and GraphicsMagick are a pair of open-source projects that forked. The utils/woptipng.py script needs the convert tool from either of these projects to remove non-pixel data from the file.
OptiPNG is an open-source image compressor.
AdvanceCOMP is another open-source image compressor.
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 is lightweight, portable, and entirely freeware. Supports many different image types, color palettes, and alpha channels.
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.