If you're just learning about photography, I wouldn't worry to much about the camera body. If you're like most amateurs, your camera will exceed your capabilities for at least a couple of years.
Today, the only reasons to go Canon or Nikon are the lenses; Sony, Pentax, and Olympus have matched (or exceeded) their feature set for camera bodies. That isn't to say the other brands don't have good lenses (quality is very similar); it's just simply that the market for Sony/Minolta, Pentax, and Olympus lenses are much smaller (new and used), and you'll have fewer choices.
Forget all the numbers on the specs sheet and go actually hold some cameras in your hand. Try finding a local camera shop; otherwise take a trip to Best Buy, Circuit City, etc. Which one feels most comfortable in your hands? How is the size/weight? Which viewfinder do you like the best? How is the placement of the camera controls?
Ergonomics should be the #1 concern of a photographer; if the camera feels natural, like an extension of your body, you'll take better photos.
Once you've narrowed down your preference of brand/body, it's time to pick lenses. I do recommend buying the body with a kit lens; most kit lenses on the market today are of very good optical quality. The kit lens generally covers the 18-55mm range; *if* you want to shoot wildlife, sports, or other items from a distance, get a telephoto. Good telephoto lenses run from $300-$500. If you want to shoot portraits, things in low-light, pick up a prime lens. Most manufacturers have very inexpensive 50mm prime lenses with a maximum aperture of f/1.8, which will allow you to shoot in much lower lighting conditions than your standard zoom lens.
Third party lenses are generally inferior to first party lenses, but there are a few gems that are an excellent value for the price. Tamron, Tokina, and Sigma all have their gems; look at FredMiranda for lens reviews.
If you want me to just tell you what to buy: go used. Since PMA 2008 just came and went, lots of people are dumping their DSLR bodies for LOW prices. I've seen Nikon D50 and D70s for under $300 for the body; that leaves $500 for lenses. Canon Rebel XT are also around the $400-mark for bodies. Pentax bodies should be pretty cheap too.
A few misc. notes:
Canon and Nikon put image stabilization in their lenses; Pentax/Samsung, Sony, and Olympus put image stabilization in the bodies. That means every lens you attach to a camera with in-body stabilization will be stabilized. That is one selling point.
Another selling point in live-view, which means you can compose your image on the rear LCD; some newer models have this...people either love or don't really care for this function.
If you want to buy a new body, I suggest waiting just a little longer; Canon is releasing the XSi, and Nikon is releasing the D60; both great options, both with new image-stabilized kit lenses (the older models have non-stabilized kit lenses).