Pedals are one of the most important components on your bike, in my opinion. They are the point at which power is being transferred from you (the engine) to the bike (the vehicle).
If you are spend a large amount of time cycling then I think that 'clipless' pedals will make more of a difference to your comfort and technique than any other piece of equipment!
The name 'clipless' is a bit misleading because clipless pedals actually have clips on them! The reason for this naming is historical. In the old days (10 years ago??) the most common type of pedal was those with 'toe-clips' which were metal or plastic clips that were attached to the pedal and came up and around your feet. Clipless pedals introduced a mounting system that didn't require these clips, so they were called 'clipless'.
Toe-clips are still used by a lot of people as a simple and low cost way to get some of the benefits of clipless pedals. The most common type of pedal used is the newer clipless system.
The way these pedals work is you have special cycling shoes that have a cleat (pointed plate of metal or plastic) screwed into them. The pedals themselves have a latch on them. You slide the cleat into the latch and then push down to clip it in.
Now when you pedal your foot stays in the same position on the pedal, which makes for a much more efficient and comfortable pedal stroke. If you want to escape the clutches of the pedal then you twist your foot outwards and it will be released. This will generally happen naturally in the event that you crash.
Generally, you can adjust the tightness of the pedals. If you tighten them right up then you have less of a chance of pulling out accidentally but if you crash then your bike will probably come with you.
Most pedals also have an adjustable 'float', which is how much your feet can rotate on the pedal without any resistance. The original clipless pedals had no float whatsoever and some people prefer this. Most people tend to go for some level of float though as this allows your feet to naturally find a comfortable position on the pedal (as opposed to having to adjust the cleat position manually until your find a comfortable position).
Traditional clipless pedals designed for use on road bikes will have a large cleat mounted to a shoe with a stiff, flat sole. This gives a very solid platform to pedal on but the shoes can be quite hard to walk in. The pedal itself can only be clipped into on one side. There are a LOT of different pedal/cleat systems, the most common are probably LOOK and Shimano SPD-SL .
If you use traditional LOOK road pedals then you can get float by using their red cleats, or you can get no float by using the black cleats.
Most mountain bikers will go for a double-sided pedal system which enables you to clip in to either side of the pedal. This is useful in tricky situations that mountain bikers are prone to find themselves in. This type of pedal generally has a small cleat, so the cleat can be mounted flush with the bottom of the shoe, making them easier to walk in. Lots of road cyclists prefer these as they are easier to use. The main downside is the added weight of two clips per pedal, and a smaller contact area due to the reduced cleat size. The most common double side system is Shimano SPD.
Crank Brothers have an innovative and patented FOUR side entry pedal which has a very simple design. These are called egg-beaters and are apparently very good with mud, so would be great for mountain biking.
If you want a reliable, easy-to-use pedal system then I think a double-side SPD based system is the best choice. This can be used on any bike and you can get shoes for this system that are easy to walk in. You can even get shoes that look just like regular street shoes. An egg-beater system would also be a great idea if you have the cash.
If however, you are willing to sacrifice some easiness of use and the ability to easily walk around in the shoes then I would consider a road pedal system such as LOOKs. I have been using LOOKs for about 6 months now and have found them to provide a more solid pedalling platform and a much nicer feel when pedalling. They are also a lot lighter, but this doesn't really make much of a difference in the majority of cases.
Update: Since writing this, my bike with LOOKs was stolen, and my new bike has Shimano SPD-SLs. They feel pretty similar to LOOKs while pedalling. In my opinion, they are harder to clip in with, but much easier to walk in.