Here's the deal - the AGP/PCI bus is shared. All AGP/PCI device data runs through the same data lines on your motherboard. This obviously makes a bottleneck situation where the devices must take turns to transmit data. Quite inefficient.
What PCIe does is allow each device their own data path. This is a giant leap in PCI bus technology, especially for video cards which transfer several gigabytes of data per second (which is why video cards were so quick to adopt the new standard). PCIe isn't just for video cards, though. Eventually PCI will be completely replaced with PCIe. This is where the different sizes come in. PCIe can come in x1, x2, x4, x8, x12, x16, and x32. I believe x64 is coming soon, but I didn't find any info on that. In any case, the numbers define the number of data paths. x1 transmits data back and forth on one data path, x16 transmits on 16 data paths, et cetera. The smaller PCIe sizes will probably be used for things like NICs, USB cards, sound cards, things like that.
Also, an answer about PCIe having fewer pins - I quoted this from one of the articles below: "In order to transmit PCIe packets, which are composed of multiple bytes, a one-lane link must break down each packet into a series of bytes, and then transmit the bytes in rapid succession. The device on the receiving end must collect all of the bytes and then reassemble them into a complete packet. This disassembly and reassembly happens must happen rapidly enough to where it's transparent to the next layer up in the stack. This means that it requires some processing power on each end of the link. The upside, though, is that because each lane is only one byte wide, very few pins are needed to transmit the data. You might say that this serial transmission scheme is a way of turning processing power into bandwidth; this is in contrast to the old PCI parallel approach, which turns bus width (and hence pin counts) into bandwidth. It so happens that thanks to Moore's Curves, processing power is cheaper than bus width, hence PCIe's tradeoff makes a lot of sense."
Here's some good reference:
http://arstechnica.com/articles/paedia/hardware/pcie.ars/1?94142
http://www.pcstats.com/articleview.cfm?articleID=1087
http://www.cooltechzone.com/index.php?option=content&task=view&id=506&Itemid=0&limit=1&limitstart=0
http://en.wikipedia.org/wiki/PCI-Express