Keep in mind the differences between X Window managers and Desktop environments..
Gnome and KDE are both projects to build full fledge desktop environments. They aim for ease of use and full functionality. They provide games, windows managers, background proccesses, file managers, volume (think like a disk or remote share) managers, sound/music applications, multimedia applications, office programs, desktop search, etc etc. They aim to be on par or superior to the latest and greatest from OS X or Windows...
This means that they are not terribly low-resource computer friendly without a lot of work.
Personally I have a gnome CentOS desktop at work running on a 300-400mhz machine with 128 megs of ram. It's definately a usable system, but it's not what I would consider 'pleasent'. If you have lots of applications running it will get bogged down.
I expect that for either KDE and Gnome the minimal you want for a positive experiance would be between 256 and 512 megs of RAM on a 800-1.2ghz machine depending on your expectations and how many concurrent things you like to run. 512 megs should be absolutely usable.
Now there are low resource desktop systems, like XCFE which is pretty much like a 'Gnome light' and is GTK based.
Now remember the differences between Window manager and Desktop Environment now.. A Window manager just controls window placement and window focus and sometimes basic menus for launching applications and WM configurations. Both KDE and Gnome have their own WMs.. Gnome uses Metacity Window manager by default and KDE uses Kwin.
Some people prefer just to use a Window Manager by itself. Instead of using Gnome + Gnome apps + Gnome background processes + Gnome Metacity Window Manager they will just use something like Fluxbox Window manager and forget the rest of everything.
Needless to say using a 'minimalistic' environment by just using a Window manager and your favorite applications will save a lot on resources.
Some Desktop Environments:
KDE:
QT based Desktop bent on modern Windows/OS X-style full features, customizability and integration by using KDE specific applications.
Gnome:
GTK using desktop bent on modern Windows/OS X-style full features, ease of use, and integration by taking popular/major GTK applications and making them comform to Gnome "Human Interface" guidelines and usability studies.
Window Maker:
The 'other' GNU desktop. It is based around GNUStep system, which is a open source implimentation of the OpenSTEP programming API. Openstep is based on the development of NextSTEP which was a commercial Unix system created by a company owned by Steve Jobs which he created after being kicked out of Apple. Nextstep was eventually to see big financial problems and was bought by Apple which returned Steve Jobs as CEO of Apple and Nextstep/Openstep formed the based of 'Cocoa' used in OS X. GNUStep and Cocoa have a high degree of programming interface compatability. It's much more lightweight then either Gnome or KDE but I think it's much more dated feeling. It's still popular.
XFCE:
A 'fast' GTK-based desktop environment. Focuses on standards, modularity, and low resource usage. Very popular. It's very nice for people who feel that Gnome is bloated, but don't want to go out and buy a new computer just to 'fix' it.
I think that those are the most common. Commercially the only ones that count are KDE and Gnome and it's more and more Gnome everyday.
There are still others...
Enlightenment, a fancy beta-status desktop..
Fluxbox, a minimalistic Window manager with panel and menu features.
Blackbox, original 'box' WM. Fluxbox forked from it after a long period of development inactivity, which has picked up somewhat..
Openbox, a 'box' style window manager that was pretty much re-written for the purpose of being EWMH standards complient so you could use a '*box' style environment with KDE or Gnome Desktop environments. To use it you substitute out the DE's native window manager with openbox. (openbox --replace)
FVWM, a classic Unix Window manager still in active development.
FVWM-95, a hack to replicate Windows 95 feel for people unfamilar with Unix window managers.
ROX desktop, a lightweight desktop system based around a file management system and focuses it's functionality around drag-n-drop
IceWM, a minimalistic Window manager that provides a Windows 95-style taskbar and start menu. Very nice for low resource machines like handhelds or older PCs.
Ratpoison, a ultra-lightweight window manager that is designed to eliminate the use of the mouse as much as possible. It would baffle most people and is designed to replicate the functionality of the terminal program 'screen' for X.
Ion3, a ultra-lightweight window manager designed around tabs-based window management system for advanced users.
xpde desktop environment, a desktop environment designed to replicate Windows XP for end-users who are only familar with XP and are migrating to Linux or prefer the XP style setup.
Then there are many others besides that. Those are just the ones that stand out in my mind.
When you are starting off just stick with KDE or Gnome.
As for KDE vs Gnome it's very much personal choice.
People _generally_ either like using KDE and hate using Gnome or visa versa. It's very paticular. Then again lots of people hate using both and that's why you see all the different smaller projects. I personally prefer GNOME.
Gnome from KDE to Gnome and visa versa is almost like choosing a entirely different operating system that just happen to have the common core around Linux and GNU environment.
Also choose them based on applications. For instance if your like using mostly KDE applications then it makes sense to choose kde, especially for performance.
When you start either a KDE or Gnome application outside of it's environment it will start up a lot of stuff in the background and load up a lot of extra stuff that will consumer memory. KDE is worse at this then Gnome stuff, but it happens to both..
So a 'pure' KDE environment is a lot more lightweight then if you were to run a bunch of GTK apps in KDE. If you run a bunch of KDE apps in Gnome then it's like your running a full gnome environment plus about 50% of KDE.
Some things to look for when running KDE or GNome to make them easier on older machines:
Lots of the small tools and toys can consume resources.. Some things that make a system more 'heavy'. Running beagle desktop search is a big one.
Running a bunch of 'applets' in your tool bar.. Those tend to consume more resources then they should. Like if you run the weather report applet to retreive tempurature readings and display a radar map if you click on it can consume a lot of RAM depending on what version you are using.
Anti-aliased fonts (mostly only realy impact slower mahcines). It's better to get nice fonts, choose 'best shapes' and go and into the more advanced settings and adjust DPI to match your monitor resolution if it's not setup correctly.
using 16bit graphics vs 24bit (24bit in Linux is the same as 32bit in Windows. 16bit colors are a LOT more easier going on older video cards.. Especially things like the Neo Magic graphics chips common in older laptops. Modern cards will be unaffected and it would be better to stick with 24bit colors)
And like I said above running a bunch of Gnome stuff in KDE and visa versa.
Using fancy animations (most in KDE) can slow things down. Also some types of themes will consume much more resources (like gradients and animated buttons vs just flat colors) then other types of themes.
Differences like that can make a big difference between in usability on older machines.
I've seen a older Pentium2-style laptop go from very completely unusable mess of a system (very painfull lag in response to operator input) with a default Gnome desktop environment transformed into a little speed demon by first switching out of Gnome and into fluxbox, then non-anti-aliased fonts, then choosing 16bit colors. It was a night and day difference and put at least another year or two of usability into a ancient business laptop.
