When I first got a bike, I ended up going to a shop. I tried looking on Craig's List, but not knowing much about bikes, it was really hard to tell what was even worth looking at. Its even hard to feel if a bike is in good condition if you don't know what they feel like new. At the shop, I was able to try a bunch of different bikes and get actual useful advice from the sales person. Also came with free tune-ups for the year.
A year later once I had ridden a bit and managed to develop some opinions, I bought one off Craig's List, and sold the first one. I managed to sell it for only $75 less than I bought it for, so it didn't really cost me much.
Also, I know that around here many shops have a significant stock of used bikes; these are cheaper than new bikes, but more expensive than Craig's List. But have been attended to by mechanics and usually come with some kind of warranty. This could be a good option.
You are looking at spending 50%-75% of the cost of a new bike by buying it on CL, depending on age and condition.
As far as avoiding stolen bikes, you can do a little due diligence. Deals that are too good to be true probably are. Ask the person why they are selling it, where they got it, how old it is, repair history, etc. Obviously they could make stuff up, but you do what you can. I'm fairly certain my used one was not stolen, since I don't think any one living in a $400k house has a side job stealing bicycles.