In addition to picking the right type of bike and avoiding stolen bikes, which have been addressed in existing answers, it's important to consider whether a particular bike is well made and in good condition. Depending on the price, a few minor maintenance needs may be expected, but a single serious problem or a large number of minor problems can easily make it more expensive to get a used bike in good condition than it is worth.
Avoid department store bikes. Note that many bike shops refuse to service such bikes because they are low quality, hard to repair, and impossible to properly tune.
A quick inspection can reveal mechanical problems. The following list of common problems to look for is loosely ordered from more serious to less serious.
Frame. A cracked, bent, or dented frame affects both safety and performance. Not only would it be expensive to get a new/used frame, but removing and installing the parts from the other bike would be a lot of work. Note that creaking can be caused by a damaged frame.
Drivetrain. In addition to the cost of replacing rusted parts, a rusty chain, cog, or derailleur is a sign that a bike has been left outside and poorly maintained. Unsmooth shifting may only require derailleur adjustment or new cables (which are easy and inexpensive to replace), but a damaged derailleur is a more serious problem.
Wheels. Try spinning each wheel off the ground: it should spin smoothly for a while, and it shouldn't appear wobbly. A hub that doesn't spin smoothly may require new bearings or may even need to be replaced. A slightly warped rim can be a minor problem if there's just a broken spoke, but a severely warped or tacoed rim may be unfixable.
Brakes. Unsmooth braking usually only requires adjustment or new cables but can be a sign of a bigger problem.
Chain, tires, and brake pads. Replacing "consumable" parts is relatively easy, but a $20 chain, two $30 tires, and two $10 pairs of brake pads adds up to $100. New parts can increase the effective price of an otherwise cheap bike.