MotherBoard ASRock G31M-S R2.0

I don't think so. It doesn't say it supports Cider Mill cpus. Just Penryn, Yorkfield and Wolfdale.
http://www.asrock.com/mb/overview.asp?Model=G31M-S

P4 651
http://www.intel.com/design/intarch/pentium4/pentium4/specifications.htm

forgot:
PCI-E 16x is usually for a video card.

It would help to know what hardware you already have, and how much you want to spend on a gaming rig, to give specifics, but you will probably need a decent mid-range PCI-E video card, at least.
A Western Digital Black or Seagate 7200.12 hard drive wouldn't hurt.
1 to 2 gigs of ram.

Hi

I have looked around and found that your motherboard does support this processor, according to the compay's website below,

http://www.asrock.com/mb/cpu.asp?Model=G31M-S%20R2.0

Now you need to upgrade to BIOS P1.70 if you see any issues running your processor. The processor socket on this board is LGA 775, whereas, 775 is the number of pins on the processor socket on your motherboard (in AMD's case the pins are attached to the CPU itself).  

The CPU that you will be using is rated to run at 800 FSB (Front Side Bus) and the motherboard supports upto 1600 FSB (in overclocked mode) and the standard maximum FSB support is upto 1333MHz. There should be no issues in running this CPU.

Regarding PCI-EXPRESS x16 slot (as advised by callandor) is an upgrade to the AGP slot. Almost all the graphics cards these days have a PCI-Express interface(the slot where you will plug in your graphics card). "x16" means that your graphics card will benifit from maximum speed in terms of communicating with the motherboards chipsets (northbridge,southbridge). Now the only thing you require is a graphics card to make this into a gaming system. As advised again by Callandor your should aim for an ATI graphics product, the reason to this is that they are offering DirectX-11 Graphics card at a reasonable price factor. All your future games will be utilizing this API (Application Interface), so in-order to benifit from the maximum visuals and windows 7 DirectX-11 feature you should get a 5xxx series of graphics product.

You should consider getting a 5750 or 5770 graphics card as they are cost effective and offers descent performance at medium to high level settings in most of todays games. You might found graphics cards with different amount of ram 512MB or 1GB. Just consider while purchasing your graphics card the resolution that you will be playing your games on, if you are running on lets say 1366x768 (standard 17" TFT 720p resolution) then 512MB graphics memory will be enough to render the textures. But if you have a bigger 20" or 22" TFT and the native resolution is either 1680x1050 or exceeds this to 1920x1200 then consider getting a 1GB Ram graphics card. Chip wise 5770 1GB should be a great buy for you in a long run, you can check the details of this card below,

http://www.newegg.com/Product/Product.aspx?Item=N82E16814131328&cm_re=5770-_-14-131-328-_-Product

its also cost effective. The reason why Callandor or I havent advised you to purchase a better graphics card is simple as your CPU Pentium 4 651 processor is not that fast. You may consider upgrading your CPU in the future and might get yourself a Radeon 5850 which is great for your next-generation games.

Atleast you should know that the motherboard you have will last you long for some time :).

I hope this helps!

Forgot to advise that to add more items you should consider getting your self 4GB DDR, consider getting the below, as its 4GB and rated at PC-6400 800MHZ that your motherboard fully supports,

http://www.newegg.com/Product/Product.aspx?Item=N82E16820220293