Ever since handguns became widely used, there has been a desire for convenient means of carrying them at the ready. Holsters may have begun as simple leather pouches and loops, but they've evolved to include tough, rigid synthetics with precision-engineered spring-loaded locking / release mechanisms. Holsters are universally designed for a relatively fast draw of the weapon, as opposed to concealing containers.
Variables to Consider with Holsters
There are a number of variables to consider when choosing an appropriate holster.
Intended use: This is certainly the primary point. Do you intend to wear your holster frequently? Is it just for show, or is it for comfort while hiking? Do you want it to be rapidly accessible, or is it just so you don't have to hold your pistol in your hand while you try to set up targets at the range?
Concealment: If you need to have rapid access to your weapon and concealment isn't a priority, then you should look at a belt holster, shoulder holster, or a drop-leg holster. If your intended usage is primarily going to be concealment, then you should probably choose a shoulder holster, paddle holster under a jacket, or a small-of-the-back holster.
Retention: If your holster is going to be visible to the public, then you should give some thought as to how much you trust the people around you not to reach for your gun. You can't see the folks behind you, and in basic holsters it's not too hard to pull a gun out of them. And while this isn't a big problem when dealing with holsters made for your specific gun, when you look at universal holsters, your pistol could jump out of the holster while you're running or hanging upside down for whatever reason. The last one seems implausible unless you take roller coaster rides into account, which have anecdotally (no solid citations found) resulted in lost weapons. An approach which the military has taken for many years was the retention lanyard (a cord connecting the gun to a holster), and the simplest way to prevent a weapon from being lost is a retention strap. This strap is usually secured by either a button or velcro. That having been said, the various levels of auto-locking holsters covered later represent the current state of the art in retention systems.
Rigidity: Sometimes a softer nylon holster is ideal, while other times you may prefer rigid kydex or carbon fiber. Whatever your preference, there's a holster out there to match. One major consideration which newbie holster buyers typically don't consider, is how their holster will work when they sit down in their vehicle. A holster which is in a comfortable position for standing and running could prove quite uncomfortable when seated.
Speed of access: Some holsters take more time to get to than others. Small-of-the-back holsters are a primary example of this.
Attaching Holsters to your Body
Belt loops: These are the most common type of holster, but aren't very easy to install/remove. For an open carry or "things went bump in the neighborhood" holster, one easy way around this is to secure the holster to a belt you can readily clip on and take off, without removing your main belt. This has the advantage of being very quick to put on and remove, and not require that you undo your regular belt in order to use it. I personally adjusted my belt just wide enough to go snugly over my belt, but not so wide that it falls off my hips if I'm in my pajamas.
Molle system: These fit over and under the pattern of loops which are provided for accessory attachment on body armor, backpacks, and various bits of tactical clothing.
Paddles: These clip on over your belt and inside of your pants' waistband. They have the advantage of being easy to put on and remove, without having to thread a belt loop through them.
Shoulder holsters: These are generally more elaborate affairs than either of the above, consisting of multiple straps. The comfortable ones, in my experience, have all been made of leather. I have yet to find a nylon one that doesn't chafe.
About Locking Holsters
A locking holster is any holster which requires the use of one or more buttons/levers to unlock a gun which it is holding. There are varying levels of complexity to these locking schemes. They are typically defined by "levels". A level 2 locking holster possesses one button, without which the gun cannot be drawn. Most police departments deploy level 2 holsters at a minimum, which is why you see officers frantically clutching the side of their holster when suspects are grappling with them. Even if the suspect is significantly stronger than the officer, it will be harder to pry the officer's hand away from his holster and draw the gun at the same time.
Level 3 holsters considerably increase the difficulty in gaining unauthorized access to a sidearm by adding a second mechanism which must be released prior to the level 2 mechanism. In the case of the Blackhawk Serpa holster (presently the only level 3 holster I have access to), the level 3 mechanism is a cap which fits over the slide and hammer of the weapon.