your best bet is to check out newegg.com or tigerdirect, 2 sites I see recommended often here. price some things out.
your first big decision will be whether to go intel or AMD. intel is easy to set up and solid, AMD is about the same, but slightly cheaper, and is more overclocking friendly. be careful if you want to do any overclocking, it can be easy to screw things up.
all modern boards will have 800Mhz FSB, so you will want PC3200 DDR RAM. best to go with 2 matched sticks (same size/speed/manufacturer), to allow you to run in dual channel mode, maximizing your buss speed. for gaming, get 2x 512 sticks of RAM.
most modern boards will support SATA hard drives. it is faster, costs about the same, and is the way of the future. it is slightly harder to set up at first, but there are many threads on how to do that here.
otherwise, you need a good case with proper cooling, a strong, name brand power supply (such as antec, 400W or more), CD and/or DVD drives. none of these are particulary expensive, but it adds up.
the biggest expense could be the video card, so you might want to consider that early, to help planning the rest of the components. you will have to decide if you want to go with AGP or PCIExpress. PCIExpress is newest, and the way of the future. make sure your mainboard will support that if you want it. it is fine to go with AGP as well. the newest video cards will cost around $500, but there are plenty of good options in the $250-$350 range.
for nvidia, many here recommend the 6600GT. for ATI, I would suggest at least the radeon X600 XT.
check out the web sites of those two, and do product comparisons.
all this is totally doable for you stated budget. if you have a CD drive on an older computer, you could put it in the new one, and save few bucks.
hope that helps.