This is a topic that you can still start a ReligiousWar over, even though the deep schism it caused in the Linux community for a time has lessened drastically. These days, most everyone sees it as what it is: a matter of choice, and not even an absolute one, since you can always use programs from the other desktop under the one you're running. And even that matters less yet ever since RedHat also made an attempt to unify the two with the BlueCurve theme that provides a largely identical LookAndFeel to both desktops. So evaluate both and decide which one you want. Or ignore the big fish entirely and use something else. Have you seen XFce?
If you like KDE, you might want to look into Mandriva, a LinuxDistribution that was started because RedHat refused to support KDE in their distribution. If you like GNOME, take a look at Ubuntu or FedoraCore.