If you stick to good brands like what was mentioned above you'll get a good frame. Look through the yellow pages and see what brands you local bike shops (LBS) carry. Generally those will be the ones to consider.
GT and Schwinn are now owned by Huffy (or the company that owns Huffy), so some shops are either dropping them or are limiting what they carry (partly due to parts availability). Schwinn still sells good high-end bikes, but these will likely be out of your price range.
After the frame, you need to look for component quality. The manufacturers all pick from a similar pool on components. Shimano drivetrains (derailleurs, chain) and shifters are very popular, but you have to pick the level. Acera is a general use level, Deore is a higher grade, with LX, XT and XTR levels to divide it up (these are all by Shimano).
SRAM makes the GripShift, which used to be considered a low-end option. But many skilled riders are finding that they like shifting with them. GripShift is a gear shifter that spins on the handlebar, rather than a set of levers that you pull with your fingers. Many riders fear that, bouncing along the trail, you will accidentally shift often. But the design seems to prevent this pretty well. You'd have to try it to know for yourself, but many bike stores won't let you take a bike on a trail to test it - but ask anyway!
Starting out, you can do well with LX components (if you go for Shimano, which is a fine choice) or, dare I say it, Acera. Don't feel like you have to spend for XT or XTR because others are. There are cheaper options than Acera, so it's not low-end, just the low end of what you should consider for MTB'ing.
You will run into brand snobs who look down their nose at a bike with anything less than XTR components. Ignore them! Drivetrains wear out, so you'll need to replace it anyway in a few years. Being new, you'll need time for your skills to improve. So pay a little less now, beat it up as you fall and improve, then upgrade when the parts wear out and your skills warrant it.
For brakes, the V-brakes are very common, with disc brakes being an expensive extra on higher-end bikes. V-brakes used to be the high end and they have, and still do, stop tires for the best riders well enough. If you get serious about riding, then you can consider discs, but not now.
After that, think about the front suspension. Rock Shox, Manitou and Marzochi make good ones. Stay away from Suntour, RS or any other shock you'll find on the cheapest bikes. As with the drivetrain, you don't need the best shock you can find starting out, but it should be a good all-around performer. You'll probably find a Rock Shox Judy TT on $500 bikes. Above that, the bikes might offer a Rock Shox Duke or Psylo. The Judy TT is a fair shock for mtb'ing, but it's at the low end. Being new, you'll probably be fine with it. If you want a good, quality shock, the Marzochis (such as their Bomber shocks) are first rate.
Think about the time you want to put into the sport. If you might get discouraged after falling and getting a few cuts on your shins, then an expensive bike is too much. If you're willing to take the punishment to improve, and you have time to get out often, then a more expensive bike could be worth it.
Who knows, you might find that other distractions (girlfriend, job, baseball games, ...) keep you off the trails more than you expect. So don't pay for a Lexus until you know you'll get your money's worth.