Post-processing is about tweaking your images to make them look their best. This isn't the best shot you'll ever see (In fact, I'd normally just forget it and move on to something else), but it does show you what's possible with some work.

Software
Modern image editing software is enormously powerful and complex, and needs a lot of time to learn fully. The good news, though, is that photographers only need a part of what most programs can do, and a few simple tools can make all the changes your pictures need. This page can't take you through everything that post-processing can achieve, but it will hopefully get you on the right track.
I use Adobe Photoshop 7, the old full version. It's getting on a bit in software terms, but it does everything I need. If you want to buy a decent program the latest version of Adobe Photoshop Elements has everything a photographer needs for around £65, though there are other programs available, some of which are just as good whilst others are more basic. There are also image editing programs available free to download, such as Picasa and GIMP, and don't forget the basic programs distributed with cameras by the camera makers.
Software can do a lot to rescue images, but it can't work miracles, so try to make your pictures as close to perfect as possible at the moment of capture. This means setting a manual white balance or using a strobe to deliver good colours, using a shutter speed and aperture to deliver sharp, shake-free images, and getting close to retain as much contrast and detail as possible. If your shots simply aren't very good (And try to be both honest and iobjective when you review your pictures) the best plan is to go back and re-shoot, but if you have that once-in-a-lifetime shot you'll just have to do the best you can back at the computer.
One word of caution - too much post-processing can degrade the qualityof your image files, introducing noise and banding in areas of smooth colour, another reason to make your original shots as close to perfect as possible.
Workflow
Whenever you work on an image make a copy of the image, close the original and work on the copy - that way you can always delete the copy and start again from the original if things go badly wrong and you always have the original to compare against.
Always follow the same routine when you correct images, that way you simplify the process and make it quicker and more repeatable. Here's my worlflow:
Crop and colour first, then Tonal Range, then Contrast, and finally any spotting and sharpening
Save your finished files at the highest jpeg resolution possible or as TIFFs
Some Examples
Using the Auto-Correct function:
Here's a very simple image to polish - the starting pictue was taken at Ras Mohammed in the Red Sea. The light was good and I was able to shoot at 1/100th sec and f8 so the shot is sharp, it was taken using a fisheye lens so I was nice and close so there's decent contrast, and it was lit by flash so the colour should be good. All in all, if this image can't be made to look good, nothing can!

All image editing programs will have an automatic correction feature called something like Instant Fix or Auto-Correct or One-Touch Correct, and a picture like this is the perfect time to use it. The one-touch correct function is always worth a try with any image. If you're happy with the results, great, time saved, job done. If not, undo the change and you can get more tricky.
The Photoshop instant fix feature is called Auto Levels. Go to Image > Adjustments > Auto Levels and click on the Auto Levels option. The image will change and the colours will seem to pop out.
(Note that all the screen shots here are from Photoshop, but all image editing software has equivalent tools)

The only other issue with this image is the area of white visib
le just to the right of centre at the top of the picture, which is a reflection of part of the housing port. Photoshop 7 has two tools to deal with this sort of problem, the Clone tool and the Healing Brush. Both work by copying pixels from another place in the image and pasting them over the bit you want to delete. The clone tool is fairly direct in the way it does this, the Healing Brush looks at the pixels in the area you're replacing and smooths the edges between the exisitng and the new pixels. Other image editing programs will have equivalent tools and later versions of Photoshop will have these and other new tools for the job
Here's the image magnified, with the Clone tool positioned to paste pixels which were taken from immediately to the right of the white area.

Here's the result of the cloning

And here's the final image

More complex post-processing:
More demanding images need more work. Personally, I try to correct the colour first, then the tonal range, then get the contrast right. Colour and contrast are familiar concepts, so here's a quick example to show you what I mean by 'tonal range'. The image is a picture of the deck of Rosalie Moller taken looking vertically downward onto the deck of the vessel at the area of damage where the bomb which sank her struck the vessel. At around 35m there was never going to be much colour and the water was full of rubbish, so it's still a dull, almost featureless, mush of blue despite manual white balance and getting reasonably close. In fact, it's difficult even to see what it's a picture of!

Here's the problem. Open the levels dialogue box - Image > Adjustments > Levels - and look at the graph in the box. The left hand end of the box represents black, the right hand end represents white and the hump between represents the distribution of pixels from black to white. In this picture, there are no pixels at either end, they're all grouped in the middle of the graph. That means the image has no real blacks, no real whites, just mid-tones.

Here's the solution. Directly below the graph are three upward facing arrowheads. The left hand arrowhead is solid black, the right hand one unshaded and the centre one grey. Grab the left one and drag it to the right to where the hump starts, then drag the right hand one to the left to where the hump ends, and you'll see the image change to this:

What Photoshop does is to darken the darkest tones to black and lighten the lightest tones to white and then spread the rest of the tones between them. If you look at the Levels graph now you'll see that there is a nice even distribution of tones from black to white.

Here's the final image, it now has a good tonal range, and though it's still not a great shot you can at least tell what it is!

Most images will benefit from some tweaking of the tonal range like this, though not usually so much. Once you have the left and right arrowheads set you can move the middle arrowhead left or right to lighten or darken the overall image.
Right, here's an image that's a bit of a challenge and will require quite a bit of work, correcting colour, tonal range and contrast.

This shot has a good few faults: the subject is further away that it could be so there is less contrast and sharpness, plus a lot of empty space at the top and right-hand sides. The colour balance was set to auto so the picture is all blue/green, and it was taken on a compact camera set to a high ISO value so it's pretty noisy. All in all, I wouldn't normally bother trying to do anything with this, the image simply isn't good enough and I'd rather go back and re-shoot to get a better image to start with. Nevertheless, lets see what we can do.
To start with, lets crop out some of the empty space at the top and right. All image editing programs have a crop tool. Simply select the tool - here you select tools from the small pane left of the screen - then click and drag the frame to where you want it
and hit Enter to make the crop.

Next. colour, and to do this use Levels. From the line at the top of the screen select Image > Adjustments > Levels and you'll get the Levels dialogue box.

At the bottom right of the box are three squares, each with an eye-dropper icon. Click the centre of the three and the cursor on your monitor screen will change to en eye-dropper. Use the tip of the eye-dropper to click on something in your image that should be a lightish, neutral grey and the software will make whatever you selected light grey with no colour cast and re-do the rest of the image with the same settings. As an alternative, you could select the right hand eye-dropper and click on a part of the picture that should be pure white. The software makes whatever you selected white, and re-does the colourts elsewhere using the same settings. If you don't like what you get, click elsewhere in the image until you're happy, then hit OK.
I used the middle eye-dropper to select a grey point and used the Aladin dive computer on the arm of my buddy to get the result above. It's OK, though too red, but clicking elsewhere in the image and trying the white-point eye-dropper didn't give me any better results, so I used this image and went back to Levels to reduce the red.

At the top of the Levels dialogue box is a white slot called Channel with the letters RGB in the slot. Click on the down-arrow at the right hand end of the slot and you'll get a list offering RGB, Red, Green and Blue. Select Red and the graph in the main window will change. Under the graph are usual three upward facing arrowheads. Place your cursor on the centre arrowhead, click and hold and pull the arrowhead to the right. The balance of red in the picture is changed and the overall red cast goes, so just move the centre arrow head until you're happy and hit OK.
Time to put some contrast back in. Open the Curves dialogue, Image > Adjustments > Curves.

When the dialogue box first opens the line though the centre of the graph is straight from bottom left to top right. Use the mouse to click on a point about a quarter of the way up the line and pull the line down a little bit, then click on the centre of the line and put the point in the middle of the box, then click on a third point about three-quarters of the way up the line and lift the line a little bit. You'll see that the line is now a gentle, shallow S-shape and your picture has more contrast as the software has made the dark shades darker and the light shades lighter. Play with the amount of S-shape you use, and hit enter when you're happy.
(This method boosts contrast without affecting the extremes of light and dark but is pretty much restricted to the full version of Photoshop or newer versions of Photoshop Elements, so if you don't have a Curves tool use the Contrast tool)
I said at the start the image was a bit noisy because it had been taken at high ISO on a compact camera.
Photoshop has some basic noise filtering tools, or there are specialist noise-reduction programs on the market, and they all work more or less well. Noise reduction works by smoothing the image, and is likely to remove detail along with the noise because the software can't tell the difference, but the specialist third-party stuff can do an excellent job and may be worth buying.
The Photoshop tools are found in Filter > Noise, and the two options we're interested in are Despeckle and Dust & Scratches. Despeckle is a simple one-size-fits-all auto tool - it's worth a try, but don't expect miracles. Dust & Scratches is more use. Keep the pixel size small, say 1 pixel, and then use the Threshold to limit the effect of the tool, using the maximum you can and still see the effect. Here the values used were Radius 1 and Threshold 18.

The result is fairly subtle, but there's still a reduction detail, and overall I prefer the version with a little more noise.
With noise reduction

So, here's the finished picture. It isn't perfect, but you'll see much less impressive shots posted with pride on diving forums every day.
No noise reduction

Original image

Sharpening:
Here's the starting image, a crop of a picture taken at Stoney Cove. It's near 100% magnification and shot on a compact, and like most digital images straight from the camera it looks a little unsharp.

In Photoshop do Filter > Sharpen > Unsharp Mask

This opens the Unsharp Mask dialogue box - Unasharp Masking was a technique devised to make photographs printed from negatives look sharper by using a mask of an unsharp image, hence the odd-sounding name. Forget that, this is the best sharpening method in Photoshop.

You'll see three sliders at the bottom of the dialogue box, labelled Amount, Radius and Threshold. Set the Radius between 0.5 and 1.5, the Threshold to 1 or 2 and then keep the Amount below 100 for best results - play with the three settings until you're happy, then hit OK. You can see the result of your changes at any time by putting your cursor over the magnified image taking up most of the dialogue box and pressing and holding the left mouse button. This will show you the image without your changes, and reapplies them when the mouse button is released.
Here's a before and after - bear in mind this is aggressively sharpened to make the point, it really needs to be more subtly done than this!


Selective contrast and shapening
As an alternative to sharpening the whole image, with any picture of living creatures you can try selectively increasing the contrast and sharpness of the eye section, it can produce results out of all proportion to the amount of work done.
Thanks to Tim Digger for this suggestion

On the left is the original image, on the right just the eye has been sharpened and the contrast boosted a little, lifting the whole picture without the possibility of introducing processing-related artefeacts.
To select an area to work on, click the Lasso tool and draw around the area you want to select. To make your changes blend into the rest of the image without an abrupt transition go to Select>Feather and type in a feather radius in pixels. A big value, 100 or more, will give very subtle blending, a small value will make the changed area more obvious. Experiment until you're happy with the results.

Selecting an area to work on: here I've used the Lasso tool to draw around the eye - you can see the dotted line around the area - and I'm about to select a feather value. Once that's done any other changes are only applied to the selected area, which can be as large or as small as you like.
Red Sea Photography Trips