PCI-E is the slot or interface that your graphics card goes to. It connects to the processor/CPU through a hyper-transport. x4 and x8 is the bandwidth of the slots, so x16 will be faster than x8, x8 will be faster than x4 and continues...
Anywhere you put the GPU, on x16/x8/x4, it would be fine, but will be slower when you put it on lower bandwidth.
Usually entry level (Sub $100) will be fine with x4 with minor bottlenecks
Mid range and high end cards (From $100 Up to $500) usually be fine with x8, just cards like 7970 or GTX 580 face bit of bottlenecks I think.
Extreme Cards (Above of $700), to be save without bottlenecks, need x16.
Basically all you need is x8, except you buy extreme cards like HD 6990 or GTX 590.
EDIT: Forget on the track of the thread...
All you actually need is PCI-E 2.0, but if you can get a same motherboard with a PCI-E 3.0 support in it, go with that. It's usually a $10 maximum difference. But when you have to buy a Sandy Bridge-E and a X79 Motherboard for example, there is no point of that. Go get a P67 and i5-2500k if this was the case.
But as I said if you can find a good PCI-E 3.0 Motherboard which the price is not far (Max $10) from a PCI-E 2.0 one, it's good to have it.