Picking a camera bag is a bit like picking a purse. There is one for every occasion and you probably need more than one. The main categories of camera bags are backpack, sling bag, toploading.
I prefer camera backpacks (ex: I have Lowepro Fastpack 250 and Kata Sensitivity V) because it's easy to access the camera and I don't kill my back by using a shoulder strap. But it's extra luggage if you are traveling. I like camera backpacks with a lower camera compartment and an upper compartment where I can put other stuff. I also like the backpack to have a laptop compartment. Not that I would want to carry a laptop while I'm shooting, but it's handy if I travel on an airplane or if I want to put a folder with paper in it (the other compartments are too small for an 8.5" x 11" sheet of paper). I'm not a fan of the one huge compartment that you fill with camera equipment and lenses. But lots of pros use this type of bag.
Sling bags (ex: Lowepro Slingshot) are smaller than backpacks. They are called "sling" because they give you the option of quick access to your camera. Some backpacks may claim to give you quick access to your camera, but sling bags are much better for this feature. However, they only have a single shoulder strap, unlike a backpack which evenly distributes weight.
Toploading bags are similar to sling bags (easy access to camera and one shoulder strap)... except toploading bags are only meant to carry the camera with one lens attached. There's no room for an extra lens. If you're traveling and can't carry an extra backpack, you could put your camera in a toploading bag and put that inside of a large backpack.
Kata has a new bag out called the Sling Backpack which supposedly can be used as both a backpack and a sling bag.
Other types of bags
Shoulder bags are kind of like really bulky messenger bags. I don't see why anyone would buy these. They aren't great for quick access to your camera. Also, there's the temptation to put too much in a shoulder bag and you will end up destroying your back. Beltpacks are for carrying your camera on your belt. It's an interesting idea, but I've never tried a beltpack. One worry I have is that the beltpack will get in your way or whack into people.
I should mention a few considerations in choosing a camera bag. One issue people often bring up is that if your bag looks too much like a camera bag, it is more likely to be stolen. My Kata Sensitivity V bag looks nothing like a camera bag and in that sense it's great. It also looks very stylish and I get compliments. I napped in a Starbucks once with my Kata bag at my feet and it wasn't stolen. Crumpler bags are also known for being very stylish and not looking like camera bags.
Another issue is whether the bag will fit under your airline seat. Never put a dSLR in the overhead compartment (my camera lens was damaged and it cost $200 to repair).
Also, I found that if my camera bag was too bulky, I was constantly knocking into people with it. A camera bag with a slim profile will help avoid this problem.
The three big camera bag companies are Lowepro, Tamrac, and Kata. Lowepro and Kata include a rain cover with some of their products, which is nice. However, you can always buy your own rain cover. Kata makes the most stylish and innovative products. You can't go wrong with any of these companies.