Saddles are a very personal choice, so what works for you may not work for me. First, do you need a different saddle? Spend some time on your bike, especially if you're new to cycling, and find out what you like and don't like about your current saddle. Once you have some miles in your legs, go out for long rides (4+ hours) on consecutive days. How does it feel at the end of Day 1? The start of Day 2? The end of Day 2?
Now you have some idea what you like and don't about your saddle, and can look for a new saddle if needed. Saddles vary in different ways: stiffness, width, and shape (top, side, and front). A softer saddle will feel nice and comfortable for short rides, but you may find yourself sinking through it and sitting on a poorly shaped frame after a while. I strongly suggest looking for firmer saddles for touring, they will not change after a long day or three.
Saddle manufacturers are only recently beginning to recognize the effect of different widths again. On your current saddle, do you feel like you're falling off both sides? Or is it so wide that it's interfering with you pedaling? Measure your saddle and look for ones that are similar, wider, or narrower as needed.
Now that you've got a saddle firmness and width that you like, choose the saddle shape that works for you. From the side, saddles can be flat or hammock-shaped. From the front they can be flat or sloping downwards. From above they can be T-shaped or triangular. Pick what works for you.
Everything else is little more than window dressing. With the proper shape, a cutout should not be necessary, but they don't hurt either. Some riders like rough coverings that they don't slip around on, other riders like smooth coverings so they don't get sore spots. For a touring bike, the rail material is unimportant as long as you avoid super-light racing rails.
Personally I like very firm saddles with a moderate width, and that are flat and have a T-shape. For plastic saddles, I find Specialized's line to work very well. Others I like are Selle Italia Flight and Avocet saddles. For expensive leather saddles, both the Brooks Pro and Swift have treated me well.
Edited for all those typos
This message was edited by wanderingwheel on 9-12-08 @ 7:27 AM