Well, to answer your first question:
If a motherboard has a PCIe slot, it it compatible.
And for number two:
If you have an intel processor, or prefer one, intel compatibility will get you farther than an AMD one, or vice versa.
For budget without overclocking, look at price around $50-75 USD with the proper socket type for your cpu, and PCIe slot for your graphics solution. Also look at the number of other features, such as DDR2 standard (667 or 800 are common) as well as the number of internal IDE or SATA connectors. If you have more than two IDE optical or HDDs, you may opt for a board with two connectors (total of 4 devices).
But since it sounds like you're upgrading from a low end system I would first start with a simple and (relatively) inexpensive RAM upgrade. This would provide you as the end user with the most noticable difference/upgrade in performance.