A regulator is usually among the first pieces of dive gear that a beginner will buy. Often, with a little help from your sales representative, you will be coaxed into buying much more in this department than you really need, and skimping or putting off purchases in other areas that would benefit you much more. This is a shame since much of the other gear you buy will make much more of a difference to you when you are actually in the water. Before you dismiss this statement as heresy, please consider my reasoning.
Why have I placed regulators so far down on the list of priorities? Isn't this the single most important piece of equipment you have? The one your life depends on? Yes, it is. And because of this, all the manufacturers have worked very long and very hard to improve their regulator designs. The result is that today every major manufacturer produces excellent regulators, and as long as you stay away from the real cheap ones, it is hard to go wrong. Regulators are a lot like personal computers nowadays - in the end, there's not much difference, despite all the hype and marketing. For this reason, I don't think that your choice of regulator is as important as your choice of many other parts of your diving kit, and I have placed it rather low in the list of priorities.
A regulator is divided into two pieces: the first stage, which goes on your tank valve, and the second stage, which goes in your mouth. The first stage throttles the tank pressure -- 500-3500 psi -- down to intermediate pressure -- ambient + ~150 psi. Intermediate pressure is also known as low pressure (LP) as opposed to high pressure (HP) which is inside your tanks. The second stage reduces this pressure down to ambient, for breathing. The first stage also supplies intermediate pressure air to your various inflators, and high pressure to your pressure gauge, although this is just a pinhole's-worth.
2016 Update
A lot of manufacturers have left the market in the last 20 years, but the recommendations below still hold true for whatever brand you are looking at. A regulator is a hunk of brass filled with springs, o-rings, and fiddly bits, and the basic design will probably never change.
First stages come in several forms. Your main options are generally:
balanced or unbalanced
piston or diaphragm
sealed or unsealed
Manufacturers will try to make a big deal out of these and various other features. Here's what I think:
balanced or unbalanced - Today only the very cheapest regs are unbalanced designs. Breathing performance will suffer, and any reg that cheap will likely be deficient in other areas. There is no reason to buy an unbalanced first stage.
piston or diaphragm - This doesn't much matter, there are good designs that use both systems - worry about other things.
sealed or unsealed - This refers to whether or not water can enter the first stage. If water can enter, then so can sand and grit, which will inevitably cause a malfunction, probably while you are in the water. Also, for cold-water diving ( not ice diving, just cold water, say 45°F ), the water inside the first stage could actually freeze, with the same result. Do not buy an unsealed regulator for use around here. In fact, don't buy one, period. Sealed designs are generally more expensive to buy and maintain, but it is worth the extra cost. Some regulators ( Genesis, Sherwood ) accomplish the same effect without technically being sealed. This is just as good, maybe better, because the design is simpler.
There are a variety of choices you can make here, mainly concerning adjustability. High-end second stages come with one, two, or even three adjustments. Some are actually useful, others are pure marketing nonsense. With thick gloves on, you may not even be able to work them in the water. All user-accessible adjustments have a much narrower range of operation than the internal adjustments that a technician can make. My experience is that if a reg is malfunctioning, the user adjustments will be useless to stop it. On the other hand, if you're a gadget person who likes to fiddle with things, some of the adjustments actually can make a noticeable ( although not essential ) difference in breathing. On the theory that extra moving parts are extra failure points, I would avoid adjustable regulators, but that's not really possible anymore. With most manufacturers, the non-adjustable regs are the bottom of the line, and you don't want that, so buy a good reg, and if it has a few useless bells and whistles, live with them.
A "same-source" octopus is an extra second-stage regulator that attaches to the same first stage and air supply as your main regulator. Your own same-source octopus is only useful to your buddy, and then only if you are together. The only same-source octopus that will be of any use to you in an emergency will be your buddy's, not your own, and again, only if you are together. In the tropics, where you can see your buddy 100 ft across the reef and the likelihood of getting separated is slim, this scheme can work very well.
However, in the low visibility conditions of the North Atlantic, counting on your buddy to be there with your emergency backup air supply when you really need it is courting disaster. You can not and should not rely on any air source that is not on your own back.
Apart from the general guidelines above, I don't recommend any particular brand or model of regulator over any other. I have used many different regulators that all worked well enough. I don't think it matters. Just remember - you get what you pay for.
With regard to octopuses: if you are on a budget, buy a better ( ie: sealed first stage ) regulator without an octopus, rather than a cheaper one with it. A same-source octopus typically adds $50-$100 to the initial cost of a regulator, plus $15-$25 annually for "service", and is completely useless. Should you later need true redundancy for local diving, do it right and get a pony bottle and second complete regulator.
Hose protectors are those funny rubbery tubes that fit over the ends of your air hoses. Their purpose is to prevent the hose from being bent sharply at the connector, which will eventually cause it to fail. However, they are practically impossible to put on. Here's a hint that makes it easy:
Soak the hose protector for a few minutes in not-quite-boiling water. This will make it much more soft and pliable. Then fish it out and jam it onto the hose quickly before it cools and hardens. Be careful not to get water in the hose orifice. Maybe I'm slow, but it took me quite a while to figure out this simple trick.
The scuba industry has successfully convinced the diving public that annual servicing of regulators is essential for your safety. Actually, at $50-$100 per regulator per year, annual servicing of regulators is far more essential to their bottom line than it is to your safety. Am I so cheap that I would risk my life to save less than $100? Not really.
All this is mixed up in business, economics, liability, and the fallacious buddy system. As you know, in the buddy system your buddy is theoretically your backup emergency air supply underwater, insuring not only against out-of-air situations, but also against equipment failures, and therefore you need only one tank and regulator. In keeping with this theory, you are sold a wholly inadequate breathing system with no built-in redundancy at all. Then, to try to reduce the inherent danger of diving with such a system, or perhaps just the legal liability in promoting it, you are then "required" to have it "serviced" at least once a year, whether it needs it or not. In fact, this is the icing on the cake for the industry, since such servicing is far more profitable than sales! The real purpose of all this is to lower the entry cost of diving by several hundred dollars, expand the customer base as rapidly as possible, and maximize revenues, and all this is done at the expense of true safety. In an industry that professes to be obsessed with safety at all costs, this hypocrisy is almost beyond belief. ( I'm not saying your local dive shop is evil, but he'll go right along with the industry-standard because everyone else does, and he needs to make a living. )