KDE uses the QT widgets developed by Trolltech for the basis. It's written in C++ and is licensed under the GPL. They incorporate as much functionality into those large Qt libs.
Gnome uses the GTK widgets originally created for Gimp. It's written mostly in C, but Mono is now a official part of Gnome and it has apps written in C# and Python. They have more dependancies and tend to have lots of little libraries.
KDE tends to develop it's own K* flavored applications. Koffice, Konqueror, Konsole etc. They shy away from external dependancies and generally do most of the desktop by themselves. They aim for completeness, uniformity, and configurability.
Gnome tends to incorporate 'best of breed' programs that use the GTK toolkit and will incorporate external stuff quicker. Originally designed as a panel, then a desktop that does everything for everybody they changed focus years ago with usability testing done by Sun, then by Novell, to have strong HIG (human interface guidelines) which empheses simple and consistant user interfaces.
Traditionally KDE has used a bit less ram then Gnome, but now Gnome is mostly caught up to them.
Currently KDE is under going a huge transition from using the Qt 3.x libs to Qt4.x. This requires porting aplication to a new incompatable API and they are using this oppertunity to create KDE4, which is going to aim for incorporating massive amounts of new software technology to make making advanced multi-media rich applications easier, while gaining more from things like hardware accelerated vector-based graphics while trying to retain the same performance people expect from KDE3.
Gnome is slowing growing and attempting to further refine the desktop. They see no need to undergo any huge changes. There recently has been a movement to reducing memory consumption and make Gnome more suitable for embedded graphical systems. (example Nokia M880
http://www.linuxdevices.com/news/NS9981902594.html )
I don't use KDE because it makes my eyes bleed, but other people like a lot.
With a good distro you can install them easily side by side and run KDE apps in Gnome and visa versa. Keep in mind that this require more memory then running one by itself. Also you can switch back and forth (by selecting a different session on login).. So that way you can choose which one you prefer.
Other desktop environments for Linux besides KDE and Gnome are:
Rox-desktop, Risc computer-like desktop.
Window Maker, Gnustep's OpenStep desktop (ala NextStep)
XCFE, performance oriented GTK desktop.
Enlightenment DR0.17, advanced graphics oriented desktop in beta versions.
Then there are minimalistic environments based around just a window manager with out lots of extra programs...
Ratpoison,
Ion3,
Fluxbox
Afterstep
And many many others.