Most underwater pictures are disappointing for the same reasons, the subject is too small, the overall picture is too blue or too green, there's no colour except that overall blue or green haze, there's too little contrast and nothing looks sharply focused.
These problems have the same cure - get closer to your subject...
...and when you're as close as possible...
...get even closer!
Oh, and stay shallow.

Taken just a metre or two below the surface, manual white balance, fisheye lens
It helps if you can use ultra-wide lenses or shoot macro, anything to reduce the amount of water between you and your subject. Water reduces contrast and removes colour. If you're more thana dozen feet from your subject the images will be dull and lifeless. Not all your subjects allow you to follow these guidelines, but keep them firmly at the front of your mind, they're about the only rules of underwater photography that really are rules.
The next things to think about are what make the difference between great shots and shots that are just OK, Lighting and Composition
Lighting
Manual white balance is surprisingly effective as a way to produce colourful images. As you get deeper the amount of red light reduces until it vanishes completely. Stay shallow - 5m or less - and your digital camera will be able to set the white balance to deliver good colour. Between 5m and 30m (ish!) you can still get surprisingly good results and you can also try using a red filter, which can give your camera the help it needs to deliver reasonable colour. Make sure you reset the white balance manually whenever your depth changes by more than 2 or 3 metres.

Left image natural light, right image with flash - note how the closer parts of the wreck look sharper and more contrasty than the bits further away in each picture. The effect of the flash is quite obvious!
You can use flash at any depth, and below 30m (Maximum, dependant on the conditions and the effect you're trying to achieve) you'll need flash. In my opinion flash is better than manual white balance and the use of filters, it delivers better, more saturated and brighter colour.
When you use flash set the camera white balance to sunny or shade, whichever gives you the colour you like, otherwise the auto white balance setting will try to compensate for the colour of the water and anything lit by the flash will have an odd colour cast.
Flash has two drawbacks (Apart from the cost, the size and weight of your flashguns - and eventually you will want a pair of them to get good lighting for anything except macro - and the cables connecting your flashguns to the camera being marginally less reliable than a chocolate teapot): backscatter and range.
Range is easy. You can't light anything with flash that's more than five feet (At most) from the flashgun, regardless of how powerful the flashgun may be, you can see that very easily from the shot of Giannis D above. The water simply absorbs the light and you're back to insipid, lifeless shots. The solution is to get closer.
Backscatter is tougher. Backscatter is produced when the light from your flash hits particles in the water and is reflected back into the camera lens, producing a bright point of light on the picture. The problem gets worse the further you are from the subject and the wider-angle your lens, and is probably at the very worst with fisheye lenses, but it is possible to take clean pictures with careful strobe positioning.

Two pictures of the bow of a small boat in a local lake, taken with a housed SLR and fisheye lens, with a pair of flashguns. In the bottom picture you can see the light area along the left edge caused by having the left hand flashgun too far forward and almost intruding into the picture area. This happens with all lenses but the fisheye being used here means the strobes have to be set well back. Note, though, that there is remarkably little backscatter.
The best solution for wide-angle photography seems to be setting your flashguns level with your camera lens and set back behind the dome port, then angled slightly outwards so that light has less chance to be reflected back - backscatter is caused by the strobes lighting up small particles floating in the water. Be careful you don't overdo how close the stobes are to the camera or it can shade the area directly in front of the lens and leave you with no light on the centre of the shot.

Here's a good starting position for twin strobes when shooting wide-angle: the strobes are at the same level as the lens, pointed slightly outward, and front of the strobe is level with the handles on the housing when seen from above. Take a look at my home page and you'll see a couple of shots of me in the water with my camera with the strobes arranged in exactly this way, one from the UK and one from the Red Sea.
Full frame fisheye and other ultra-wide lenses have their widest field of view across the diagonals of the frame. Most flash support arms place the flash slightly above the camera and on the same plane as the lens, either to the left or right,. This effectively puts the flash close to one of the top corners of the picture, right where it can cause the most backscatter, as well as possible catching directly on the surface of your dome. Not good. Keep the flashguns slightly behind your dome and level with the lens when seen from the front.
For very short camera-to-subject distances - such as macro shots - backscatter is almost irrelevant. You can still find it if you look hard enough but it won't intrude except in the worst conditions.

Some starter positions for macro with one and two strobes. if you use a pair of strobes simply turning the power of one down will improve your lighting.
The really bad news is that backscatter is like death and taxes, it's a fact of life, you'll always get some, and post-processing is probably the only way to truly eliminate every last little bit.
Composition
With the basic technical stuff sorted, it's time to get arty. Not really, but there are some simple guidelines that can help you produce pictures with more impact and viewer appeal.
Eyes - the first things we look for in any picture of living creatures are the eyes. They have to be in focus, and pictures always work better if the subject is coming towards you rather than going away. Get the eyes right and you're basically there. This shot of a moray would be lessened if the eyes (And teeth!) weren't in sharp focus...

The Rule of Thirds suggests that pictures have more impact if the main features are placed on an intersection of thirds. If your subject is a living creature, the eyes should be on one of these intersections. This picture of the propellor of the Chrisoula K isn't the most dynamic of shots, yet it illustrates the Rule of Thirds very well: your eye has nowhere to go but end up on the boss of the propellor, which is on an intersection of thirds.

Diagonals are dynamic, with a slope from bottom left to top right being more suggestive of growth and energy than one going top left to bottom right, probably because we're taught all about graphs at school. This shot of a diver tying-in to a wreck is full of diagonals, all running bottom left to top right, and gives some feeling of the energy needed.

Flat lines are restful and static, and times don't come any more restful or static than sunrise and sunset. Note also the central placing of the sun on the horizon line, which increases the sense of nothing much happening. Incidentally, set your whiote balance to daylight ofr sunrise/sunset shots, otherwise the auto white-balance will take away much of the colour you're trying to capture.

Put something in the foreground, it gives your shots a depth they otherwise won't have and leads the eye into the picture. People always look at human figures in a picture so be careful where you place people in your shots. Here the divers are on an intersection of thirds which strengthens the composition.

to emphasise the part of the shot you want to be the main area.
Juxtapose colours and brightness, the eye naturally comes to rest on the brighter and more colourful part of the image so make that the bit you want people to look at. On this image, follow the octopus tentacles and they lead into a nice crevice in the rocks, suggesting something of the bahaviour of these creatures.
