Clipped in, SPD style.

The clipless pedal.

Yes, you can slide your foot into a plastic sheath to keep your shoes from having to dance with about 30 spokes, but there is no rush like having your legs all but welded to the pedals of the bike while you hammer down a trail about a half-second from tenderizing your face on the gravel below. Clipless pedals can strike fear in even the most seasoned MTB rider. If you ask anyone that has them, you will hear how great they are, and how "you" need to get them right now. Most people are used to toe clips, and while they have some downsides, there is usually no hurry to get rid of them.
There is no secret that a set of SPD pedals and shoes will run close to $200. For this reason, one should be clear about *WHY* they are getting clip-less pedals before making the investment, there are advantages and disadvantages.

So why even connect my foot to the pedal to begin with?

Believe it or not, this is a safety issue. First, lets think about a simple 18 inch burm you intend to take some air off of. If you hit the berm anywhere but spot-on in the middle, you are going to need to hang on to that bike as it gets launched from the berm and into the air. Next, you have to hang on to the bike as it hits the ground on landing and keep everything upright and moving forward without getting launched towards Saturn. If you think you can do this without some sort of 'connection' to the bike, you will find yourself very wrong and very sore.

Why not Toe clips?

There is nothing wrong with toe clips. Generally, they are sufficient for most terrain and most beginner riders. The issue comes into play when you want to do some serious climbs, jumps, and descents.
The biggest problem with toe clips is the inherent danger when you do not have your foot in the clip - it hangs down and catches on things. It is not recommended to take your foot out of a toe clip when on a rough surface. The toe clip will hang down and hook itself on everything you try to ride over - this really hurts! Needing to take your foot off the pedal can also compound this. When taking a fast or loose turn, get one foot off the pedals and out to the side to act as an outrigger. This means the bike can slide and pitch about, and with a leg out, you can keep ahead of the bike and ride it out of the turn at full-steam.
If you attempt this with toe clips, the sequence is always the same - you slide your foot out, the clip catches on things, you get through the turn, and then you try to get your foot back into the toe clip and start pedaling again. Very difficult.

This is not to say that toe clips don't have some advantages over SPD-type pedal systems. The most obvious advantage of a toe clip is getting out of it. You slide your foot back and down - no problem even in a fall. You also have some float in your foot when it is in a toe clip. You can move your heel to the left and right as you pedal and hang on for dear life. This float allows a rider to get pretty sideways on the bike, perhaps to recover from a bad jump (the voice of experience here) or to keep from washing out on a turn.

Let's clip.

This is one of those "what to buy" things. There is no right answer. Most clipless pedals will be LOOK or SPD compatible. LOOK and SPD dictate the type of pedal and cleat that is used to make the connection. You can tell an SPD setup from a LOOK setup, I recommend going to a bike shop and seeing both for familiarity. About 80% of the pedals and shoes out there are SPD or Shimano Pedaling Dynamics compatible.

For the sake of simplicity, it is recommended that you choose an SPD-compatible system. Later you may need parts for your pedals, or cleats for your shoes. By choosing SPD, you will have no trouble getting the stuff you need in the future. The SPD system consists of a shoe with a metal 'cleat' screwed into the bottom of it, and a pedal, which will accept the cleat and allow it to click in. This is done rather simply. Think of the cleat as a triangle with a corner pointing towards the front of the shoe. You slide the front corner of the triangle into a little notch in the front of the pedal. The rear of the triangle (the other two corners) press down on a metal bar which yields to the pressure, moves out of the way to the back, and allows the back of the triangle to 'click-in' beneath it. You are now clipped in. To get out of any SPD, you just twist your foot outward from the bike. If you have multiple-release cleats, you can twist your foot inward or upward also.

There are a number of variables when dealing with SPD shoes and pedals. First is the type of pedal. You can get SPD pedals, which are rebuildable, and some are even made with SUPER lightweight parts. Some SPD's have 'cages' like a normal pedal, while most others are cageless. There are even SPD pedals, which you can clip in to both, or even four sides!
Some SPD's have a bit of lateral 'float' to them, usually 4 to 6 degrees - this is a function of the pedal and not the cleat as one may think. SPD cleats are a bit more cut and dry. You do have a choice of materials that the cleat is made from - usually stainless steel - but this effects only how long the cleat will last. Yes, cleats do wear out. You will need to start a memorial cleat fund if you ride a lot.
Other than that, the only option is if the cleat is multi-release or not. As mentioned earlier, a single-release cleat will only allow you to get out when you twist your heel out away from the bike. This is done so that there is little which will accidentally dislodge you. If you find you are clipped in and always stay that way, you will want the single- release cleats.
A multi-release cleat will allow you to get out by twisting away from the bike, into the bike, or by pulling upwards a bit. They are easier to get out of, and you can get disconnected very easy when the trail gets rocky.

So, how to make a decision?

The biggest hurdle with mountain biking is jumps and hard-burmed turns. On the jumps, you occasionally get too squirrelly on the take off, and find yourself contorting your body while in the air to correct for the bad launch. The jump is compounded because the feet were loose in the toe clips and you could not goose the bike to work.
Next are the turns. When there is a high-burmed turn I like to come up to it at full-tilt. This means taking a foot off the inside pedal, going into human-outrigger mode and hanging some bootie while I shred the turn and exit out with full impulse power. Problem with the toe clips is that you cannot get back into the pedals quickly and cleanly, and you’ll have to fumble a bit to get under power again.
The decision to get SPD's is easy. When you reach a point where the toe clips are impeding your ability!

I found that none of the SPD pedals were weighted too well. Most of them would rotate to the rear of the bike when you clipped out. Some would rotate to the front, and some would even rotate upside down! This means that you need to know how the pedal will 'fall' when you take your foot out so you can clip back in. Most of the Shimano SPD pedals will fall to the back. This means that the rear of the SPD pedal is the heaviest, so when you take your foot off the pedal will rotate back about a half-turn. Knowing this, you can assume that the front of the SPD pedal will be "up" when your foot is not in it. You can then enter the SPD pedal by moving your foot forward from the rear of the pedal.
The point here is to go get a set of SPD's you are interested in, and grab them by the spindle to see where they 'fall'. As odd as this sounds, no one seems to know about it, and I can see that this would be a real pain if the pedals were not behaving as you expect. If you find nothing that satisfies you, you can get a set of SPD pedals with a place to clip in on both sides!

Do you need float? What about the shoes?

There are many things to determine what you should get for SPD's. The biggest factor will be that you are new at this. Why buy something that you cannot take full advantage of?
When you first use SPD's you will have to deal mostly with clicking in and getting out. The biggest hurdle is getting out of the SPD pedals when you are about to crash. This is one thing that can take a long time to master.

I recommend a good shoe, one that fits well. The advantage to the shoe is that the insole is reinforced. By preventing the flex you get in a normal shoe from going down the sole of the shoe, you put MUCH more of your energy into turning the cranks and less into bending your footwear when you are hammering on your bike.
As to the cleats, I think you should decide what you want to use them for. If you want to clip in and stay there, I recommend the single-release cleats. If you want to come out easy, or you find yourself having trouble getting out of the single-release cleats you may prefer the multi-release cleats. Since cleats are about $20, you may want to buy both and see which one you like the best.
For pedals, you really need to only think if you want cages or not. With cages, you do not need to have your SPD shoes to go for a ride, and you can hang with the big guys in tight twisties. The downside is that you have less ground clearance than a cage-less SPD pedal. Start with an affordable, name-brand pedal. You can get the top-of-the-line pedal later. Until you use the pedal for a few *months*, you cannot expect to know 'what you want' and how you 'want it to work'. Better to buy a pair of $60 pedals to start with and then upgrade to a better set later. Besides the fact that the technology changes every 8 months, things get cheaper and better as time passes.
Remember that todays top of the line component is tomorrows entry-level component.

Impressions of the first time SPD rider:

Oddly, it was easier than I thought it was going to be. The biggest problem is crashing. Normally I try to approach things without fear. As long as you are not afraid, it is easy to keep a light touch on the bars and to moto through terrain that is trying to buck you off. When you get nervous, you will tend to death-grip the bars and sometimes you will not react the way common sense tells you to.
What I find most prevalent with the SPD's is that I am now a bit afraid of falling. As a result, I get into some stupid situations where I am not doing what is needed to keep the bike on the line. My fear stems from the SPD setup. I like to separate myself from the bike when the poop hits the cooler, and with the SPD's I have this fear I will not clip out in time, and I will have to take a fall with the bike connected to me. This has never happened, but I think about it when I ride. I know this will pass in time, but it was an unexpected side effect.
Another problem stems from the SPD pedals themselves.

You cannot buy an SPD pedal without a disclaimer in it. Every SPD pedal had a form you were supposed to sign which stated that the pedals had been installed by a pro, and that you had been trained in the use and maintenance (wd-40) of the pedal. This was, in a manner of speaking, a litigation disclaimer against the manufacturer of the product. This disclaimer is also stuck to the inside of the SPD boxes so that you cannot do anything without seeing all these disclaimers and forms. Seeing all the stuff in the box immediately gives you a sense of doom from the get go. Geez, no one lectured me about being careful when I bought my bike! You should see what I can do with it!! Why are they putting all this product-fear into the consumer about a set of bicycle pedals?
Not a good way to get new users to buy pedals as far as I am concerned.

Reciprocally, the pedals have many upsides to them.
First is the air, more air, big air. My goodness, you can catch air when you are connected to the bike! I would guesstimate that my bunny hops gained about 4 to 6 inches on day one, and I can take familiar jumps at a lower speed and catch much more air! I also have less fear on jumps because I am connected to the bike. If I leave a jump at the wrong angle, I can just use my arms and legs to put the bike back under me the way I want it to be. No more stratospheric body contortions as the bike leaves the ground and I leave the bike! Tabletops??? Weeeeeellll, no not yet, but I can get the front tire way crossed-up before landing. More on this later.

The next SPD gem is climbs. Climbing gets much easier because you can put less energy into the pedal to get it to turn. Remember that your SPD shoe has a rigid insole, and it will put all your energy into the pedal and not the sole of the shoe! This means you can use the energy you have now to climb a bit higher, or grind up a hill a bit longer. You also can pull your cranks through the stroke when climbing. This is harder than it sounds, but if you master it you can save even more energy.

What if you could move your whole bike to the left or right a few inches when the doo-doo was about to connect with a fan? Pretend you are coming up to a small ledge with an 18 inch drop-off. As you get to the edge you realize that going on the line you are on will result in getting bounced off and probably launched into space. Just before you get to the edge, you can move (hop) the bike a bit to the left or right to correct the line you leave the ledge with. Sounds much harder than it is, and you will probably surprise yourself the first time you do this. It will save your butt. On a similar note, the SPD's allowed me to take jumps and hops off a line. That is, I can leave the ground on an object and land a few inches to the left or right of it. This is also nice when you have to catch air on a turn. You can actually get into the air on the turn, and keep the bike lined up for the leaned-over landing - way cool!

Overall, the SPD's have helped my riding. Considering the cost, it helps if you are not new at this. I would not recommend SPD's for anyone who is less than serious about his or her MTB experiences. For the money you could buy a pretty radical rim, or add a suspension where there was not one to begin with. If your bike has it all, or you're real comfortable with your bike, then SPD is for you.
As with anything, be prepared to practice - SPD's are not forgiving, but if you want to reach a new level of control they are a good investment.