Most users in the States use Gnome. KDE is more popular in Europe. Gnome has been gaining popularity worldwide in the last few years because it is Ubuntu's and Debian's default.
Gnome 3 is already out, although the only people who've packaged and released it as part of their distribution as of this writing is Arch (Testing).
Some of KDE's applications are the absolute cream-of-the-crop: Amarok, the music manager; K3B, the disk burning utility; DigiKam, the photo manager are all among the best of these applications regardless of OS or DE. You can, of course, use applications using both the GTK (Gnome) and Qt (KDE) interfaces; although you'll be using a lot of RAM to do so! (And the applications may well not look very consistent relative to each other. Skype, built on Qt, sticks out like a sore thumb in the middle of my almost-exclusively GTK-based desktop. Same with Opera, KeePassX and the VirtualBox management interface.)
The two others worth taking a look at are XFCE and LXDE (both GTK); both of which are geared towards lower-end machines and which use much less resources than either Gnome or KDE.
And of course you can run your system without a Desktop Environment altogether! My Arch system, without a Desktop Environment or a Display Manager to handle logins, is beautiful, uses all of the standard applications you'd expect and uses only ~65MB RAM from a cold boot.
