For the last bike, I'd wanted to get bike racks, but I wasn't sure what would fit. The current bike came with a rack.
After a few days of biking on the new bike, I decided that, for everybody who isn't actively racing, you need a bike rack. Period. It's too useful. You can keep your center of gravity low, which is important for stability, by hanging stuff off the sides of the rack. You can strap quite a bit on the top of the rack. And all of this keeps you from needing a backpack, which means that you don't have a big sweaty mark on your back.
Rack fitting is tricky. See, back in the day, it was a little easier because enough people mounted racks that it was a consideration. You need two mounting points above the wheels and two around the seat tube, so there would be four "eyelets" brazed to the steel frame. Eventually people decided they didn't like how that looked or wanted to save weight, so you can often buy a new bike with no mounting points for a rack. The exact positioning of the rack eyelets is a little flexible, so it's always been at least a little tricky, which is racks often have screw or bendable-metal adjustments. Also, disc brakes often interfere with the shape and mounting location of the rack, so you may need an adapter or a special rack.
If you don't have all four eyelets, all is not lost. You can replace the seat tube mounts with a clamp around the seat tube, a pair of P-clamps that wrap around the seat stays, a single P-clamp that wraps around a single seat stay and provides two screw holes for the rack, or use the rear cantilever brake bosses. You can replace the wheel mount with something that mounts to the dropouts or another pair of clamps. Mind you, you still are purchasing a bike from a stupid designer because the eyelets isn't going to change the weight of the bike more than a few grams in many cases. Also, you will invariably pay more for your rack if it's special-purpose.
Keep in mind that, unless you try to mount a given rack on your bike, no matter how compatible the rack may claim to be, you still run the risk that it won't mount after all. Don't blame the rack maker, blame the bike maker.
There are racks that clamp to the seatpost and nowhere else, but this is not a very good idea. If you are riding a randonnee or other such ride and need to carry a few pounds in back, it's OK, but otherwise, it's putting a lot of stress on the tube because it acts as a lever. In my book, given that you are already using a comprised design, you might as well get an oversized under-saddle bag.
It's much much harder to mount a rack when you've got rear-suspension because you have to either mount all of the rack bits to the part that moves with the suspension or you need to mount all of the bits to the body of the bike. And if you go for the second option, you need to make sure that you won't hit the wheel against the rack on rough terrain. This is part of why I dislike full-suspension bikes.
While we're on the subject of racks, you can also have a front rack. There are some good reasons to do this. When you ride, you naturally put more weight on the rear tire. Just loading the rear rack means will further magnify this. Also, you can end up with the rear end loaded back far enough that it starts to act as a lever and pull the front wheel off the load. If you add a rack up front, you can load both front and back. Along the way, somebody invented a number that says you should load 40% of your weight up front and 60% of your weight in the back, but I doubt that's an absolute rule.
For front racks, the correct set of bosses is even more rare. You can get a lightweight shelf of a rack that hooks to the front canti-brake bosses and the bridge of the fork. You can also get forks that have low-rider rack eyelets on the fork. And you can again use P-clamps or something that mounts to the dropouts. There are a few carbon fiber forks floating around that have rack eyelets on them. I'd hesitate to try and add any sort of rack to a carbon fiber fork that wasn't built with a rack in mind.
There are a few design points for a rack.
First, in Europe, there's a standard mounting arrangement for lights. In America, there's no standard whatsoever and I see tons of racks that don't have a bracket at all. Good racks have holes that match several mounting schemes (it's not especially hard to do this) and this means that you can still have a rear reflector/light for when your cargo hides the seatpost mounted reflector/light.
Second, structural strength. Lesser racks have a habit of cracking and failing when you load it down heavily. There are touring-specific designs, but I suspect that you really find out how sturdy the rack isn't the hard way because most of them are now welded out of hollow tubing or solid bars out of aluminum and thus most of the things that will cause structural failure have to do with the quality of the welds and thickness of the tube walls, which you may not be able to evaluate non-destructively.
This is also best considered with the weight of the rack and the desired load capacity of the rack. A rack designed only to carry a few pounds doesn't need to be especially heavy or sturdy. A rack designed to carry a full loaded touring load will end up being heavy because it needs to be sturdy. Both of these are OK. However, a rack that is heavy and not at all sturdy is no good.
Third, ability to mount things. Some racks are unable to deal with a trunk bag. Some racks have a set of rails dedicated to panniers that are lower and towards the back farther such that you can get the panniers closer to the ground and farther from the pedals. I'm seeing racks starting to come with mounting points for U-locks. Some racks have spring-loaded "mousetraps" that I don't really like very much. Topeak makes a special mounting cleat atop the rack and bags designed for the rack that makes mounting trunk bags much more reliable and convenient.
Fourth, ability to double as a rear fender. I tend to prefer racks that have thin piece of something above the tire so as to prevent rain from splashing up off the tire onto the rider's back, thus preventing you from needing to figure out how to mount both a fender and a rack.
I should mention cargo bikes and trailers at this point. See, you can get bikes that have enlarged racks like the Xtracycle system or integrated cargo boxes, like the bakfiets. Or you can get a hitch for a cargo trailer. The Xtracycle is even available in the form of the Free Radical kit that will let you modify an existing bike.
Now, you can sometimes use bungee cords or twine and carry stuff on your bike. But there's also a lot of options for bike luggage.