I'm not sure there is a way to be totally sure but chances are they aren't stolen since its an older phone and most people selling them are probably upgrading. If you are worried that someone will take it away from you, I doubt that will happen since you don't have to register the iPhone with your provider, you just pop in the sim card and away you go. But do make sure you get a 3GS at least. The 3G is pretty crap on iOS4.
Actually I don't see the difference to you when it is stolen or not. Sometimes the stolen ones are sold to the retailers and get it packaged so you wouldn't be able to tell the difference. However, maybe you can ask for the receipt and warranty. Good luck though.