Briefly, KDE and GNOME call themselves "desktop environments". They set out to deliver a desktop with all the common applications people use, which are all somewhat integrated so that you can use them together. Among the two, KDE is much bigger, has way more applications and has way more momentum as well. Some people are religious about this and insist on using "only KDE applications" because they run KDE, and Gnome applications (which run just as well) look "out of place in KDE" they say.
KDE was the first one, Europe centric. In fact it means Kool Desktop Environment (ah, those witty germans

). But it uses the QT toolkit, which was originally under a non-GPL license. Which was a level of evilness some people couldn't stomach and so Gnome was started, GPL from the beginning. Gnome is more Americas centric, one of the main guys is Brazilian (Miguel de Icaza, now at Novell). It's now been years since QT became GPL, so the license problem is a complete non-issue now.
Anyway, whichever "desktop" you use you can run any applications anyway.
KDE apps of note:
Konqueror
Kate :cool2:
Konsole
Kopete
KOffice (full office suite competitor to OpenOffice)
Kontact (email, calendar etc)
Amarok

K3b (cd/dvd burning)
Gwenview (image viewer)
Krita (image editor competitor to the gimp)
Okular (pdf viewer)
Apps built with QT but not KDE-integrated:
Scribus (desktop publishing)
Gnome apps of note:
Epiphany (web browser, "very low weight Firefox")
gnome-terminal (equivalent to konsole)
evolution (email, contacts etc, equiv to kontact)
totem (media player)
rhythmbox (crappy mp3 player)
gthumb (image viewer)
xchat (irc client)
abiword (word processor)
gnumeric (spreadsheet)
Apps built with GTK but not Gnome-integrated:
Inkscape (vector image editor)
the gimp
OpenOffice
GTK is the equivalent to QT, the library used to write graphical apps. The difference between integrated and non-integrated apps is that the integrated ones use some KDE/Gnome specific features that make them "fit" more into KDE/Gnome. But generally an app looks and behaves almost the same whether it's just QT or using KDE specific stuff.
Btw among the two QT has wahaaaay better cross platform support and KDE4 is gonna be released also on Windows and Mac for the first time.