Do your homework. Some starting points for the very beginner: What labels generally put out the music you like? Artists you like? How many records/what records have been released by them? There are plenty of resources online that can help figuring things out a bit.
I'd personally advice starting by getting a few solid listenable joints to avoid possible frustration. Sure, it is fun to pick up cheap random records and it can be fruitful regarding sampling, but in the beginning of your digging career, you might simply end up with stuff you don't feel (and stuff you wouldn't want to sample too). Picking up cheap records you haven't heard of before will get easier as you build up your knowledge. And hey, if you bought something you don't feel, at least you got those solid listenable joints you got earlier.
Some useful links:
Discogs - Database and Marketplace for Music on Vinyl, CD, Cassette, MP3 and More
www.the-breaks.com, AKA The (Rap) Sample FAQ
eBay | Electronics, Cars, Clothing, Collectibles, and More Online Shopping
Soulman's World of Beats articles are a nice read too.