I haven’t used KDE for a very long time, obviously since before Fedora Core 13. Back then, the yum group for KDE was named kde-desktop, so a simple sudo yum groupinstall kde-dekstop would set you on your way.
Since FC13, the group name has changed to the not-so-obvious KDE Software Compilation.
sudo yum groupinstall “KDE Software Compilation” (with the quotes) and you’re off!
I’m installing KDE in a fresh install of FC16 as I’m writing this, because like Leonid, one of the things which annoy me about GNOME 3 is the inability to see a Skype icon with notifications of incoming chats without having to move your mouse to bottom right corner all the time. We are using Skype as an example here, there are of course other icons which one might miss, such as the Dropbox icon for example to know if any synchronisation is in progress.