One important thing to know, before we start, is Microsoft is the single source for windows software. In reality, Microsoft Windows is really multiple layers of software, working transparently as one product. In the Linux world, these multiple layers are working together, with multiple software packages available for use on each layer. Because of this array of choices, it's easy for the average user to get confused with these terms.
I'm going to try to explain the multiple layers below layers below:
1st layer - command line interface / kernel
To understand the multiple layer aspect of Linux, and describe it in simple, windows-centric terms, when we're talking about Linux, let's pretend we're back in the days of windows 95.
The "Linux" Operating System is similar to DOS where everything is executed from a command line interface (abbreviated CLI). A Linux CLI is very similar to DOS. In fact, on most server installations of Linux, a CLI is the only way to access the machine. After Linux starts up, depending on configuration, it will either stay in command line mode, or start a graphical user interface (abbreviated GUI) automatically. Additionally, on some machines that stay in CLI mode, a user who logs into the CLI can manually start a GUI.
2nd layer - Graphic USER Interface
On top of the command line interface, sit the GUI. Modern Linux systems typically use an X Server, which is essentially just like the windows desktop (think a blank canvas in Photoshop).
This layer handles the hardware level of the GUI, managing the input from the keyboard, mouse, and output to monitors, etc. Basically, it handles how things are drawn to the screen, what is drawn on the screen is controlled by a windows manager.
Windows Manager
Sitting on top of the X windows system is a windows manager. it's responsible for drawing each application on the "canvas", and attaches common window elements like borders, the title bar, minimize/maximize buttons for the window. It can also control other aspects of the program as well. Switching windows managers can be a lot like switching themes in Windows (think going from Classic mode to aero mode). The frame of the window will change, while the content of the window generally stay the same.
The most high profile window managers are KDE & Gnome, and generally a Linux distribution will focus on one window manager as the primary interface. However, in general, most distributions will install both windows managers onto your system so that they would be available to you. In most cases, you would be able to install any window manager on any distribution and be able to run it without an issue.
Ultimately, it's a matter of choice which platform you would want to use. Each provides a large number of applications that run under them, using their framework. Also important to know is that multiple windows managers can be running at the same time (Enlightenment and be used under Gnome, etc), but that's typically outside the need of normal users.
With regards to Gnome & KDE specifically, these two software projects have grown much larger than a simple windows manager. They also offer much more, including a development framework to create applications from. The KDE framework is known as Qt, and the Gnome framework is known as GTK. The entire scope of these 2 projects would be information overload.
To help confuse the issue for normal users, KDE & Gnome are now available for use on the MS windows platform, however, typically use by applications that are trying to be used on multiple platforms (like pigdin Instant messaging software). In most instances, however, when reading about Gnome or KDE, a linux desktop is being described.
Thanks to Phoshi, who's answer i build upon