Gnome and KDE are the most common open-source desktop environments for Linux. They handle much of the GUI related operations in Linux (ie opening windows, copying/pasting, games, file management, etc). I suppose you could think of Gnome and KDE as the "Windows" (as in Microsoft) of Linux, in that they give you icons you can click on, a desktop, screensavers, many useful programs, and a lot more.
Gnome which is supposed to be pronounced "Gah-nome", although I think many people just say it as it looks. KDE stands for K Desktop Environment.
Whether you use one or the other is often a souce of flaming in forums. They both offer similar features, with some differences. Some say, "The feel of KDE is different than that of Gnome", and vice versa. I find it difficult to list the differences between Gnome and KDE because I primarily use Gnome, so perhaps the links below will help.
Anyway, that's the gist of Gnome and KDE. For more information, and some nice screenshots, see http://www.gnome.org
If you use a slow computer, Gnome and KDE may be a little too bloated (ie too memory intensive), so some people like to use plain "window managers" instead of complete desktop environments. These include WindowMaker, IceWM, and more. Basically, they just allow the opening of windows.
Hope this clears things up a bit!