Your question is hard to answer with any great level of detail because it's so broad. The two main questions you need to consider are:
1. New or used?
2. DIY or prebuilt?
The third question of course is how much to spend. Personally, I'd recommend building a machine yourself using parts you've selected from a reputable vendor such as
NewEgg. You won't have to compromise on the components you want, plus building your own machine is an excellent learning experience if you haven't done it before (along those lines, it's really not that hard - there are only about 8 or 9 components to hook together and that's it)
If you want to go with a new system, then keep in mind that the very latest and greatest parts may not have as good of Linux support as older models, simply because the manufacturer may not have released any Linux drivers for them yet. Additionally, prebuilt systems often lack the same expansion capabilities of home-grown boxes, so you'll want to check that it has sufficent PCI slots, RAM slots, USB ports, etc, etc for your intended usage. In any event, these days mid-range models (and even low-end models) are way, way more powerful than most people would ever need, and most likely would be plenty good for most people. Additionally, a new prebuilt system would already be running Windows, which can be helpful if you plan to dual boot, or a completely unnecessary cost if you plan on going 100% Linux.
You can also sometimes find some amazing bargains on used PC's on places like Ebay and
CraigsList I think Brian1's suggestion about using a Live CD to test compatibility is an excellent one in terms of evaluating whether a machine seems to want to play nice with Linux.
Overall though, most PC's will work just fine with Linux.
