For a new build, I would think of what kind of performance I plan on using and what technology is involved. If you want to use PCI-e graphics interface (what type of video card you want), than of course you need a motherboard that will support that. If you want to stick to the old AGP standard, than you need to get a motherboard to match that.
Than I would think of what kind of processor to use. Intel or AMD. Most on here agrees that AMD is pretty serious when it comes to gaming. The Athlon 64 is the way to go using Socket 939 configuration. Make sure the motherboard has that capability. Then think about the type of memory you'll be using such as DDR400, etc. I like to use 1GB memory size as standard these days. Of course, is you get a power system (most likely nforce4 chipsets), it will come with all the goodies such Dual Channel memory, SATA, PCI-E support, fast transport bus, etc.
..and like Tweak said, get a good case for cooling purposes. I'm sure most mid to high end cases will be compatible with ATX motherboards. COnsider the amount of power you need to determine what wattage power supply to get.