X is a layer between applications and the OS's graphics libraries (unless you are on a Windows machine right now). Your Keyboard, Video, and Mouse (KVM) connect to the computer. After they leave the hardware level, most operating systems have a bunch of hardware drivers. Microsoft Windows connects to these drivers, and that's that. But in Unix machines, there is another layer, an X server. The X server connects to the drivers that connects to the hardware. Now say you have a program like xcalc, which we call an "X client." Xcalc connects to a graphics library, sometimes known as a Toolkit, or TK (hence the names tk and gtk). These libraries know how to talk to the X server via the X protocol, and so the flow goes like this: xcalc -> gtk - [ via X protocol ] -> X server -> OS drivers -> hardware.
Now, why have that extra layer in there? MS goes from calc.exe directly to the graphics libraries, for instance. Well, it all started back when desktop machines were tens of thousands of dollars, and often had little processing speed. When you wanted to run two programs, often it was better to run one of them on another machine. Suppose you wanted a GUI interface on that machine, though? Well, the X protocol is not just something on a local machine; it can be called over the network! So you can use the GUI on your machine, but the processing is done on the machine you are connected to. In fact, Unix doesn't care who called the X protocol. So on machine 1, you could open up xcalc, which talks to gtk, which uses to X protocol over a TCP/IP network to the X server on machine 2, and machine 2 does all the work.
Not many people use X over the network these days, though. It's a network hog (don't use it over, say, dialup... I can't image it was any better on x.25 serial-based networks [shudder]), and a majority of people don't need GUIs to run something on a remote machine anyway. So why should you care?
Because Gnome and KDE are X clients. Doh!
They are NOT "X windows," as a lot of people say. They are X clients that use the X server on the local box. This explains a LOT of errors people get when setting up KDE, for instance. Here's how KDE works, for instance.
kde [Desktop] - gdm [desktop manager] - gtk2 [Graphical toolkit libraries] - Xfree86 [X server] - OS drivers - hardware [KVM]
See, KDE is considered an X client. Not "X windows." Not a "version of X windows." It runs using X windows, but saying it is X windows is like saying a pickup truck dashboard is an engine.
A lot can go wrong in that stack, and the message boards are filled with people saying "wtf? no screens found?" and "how come my mouse doesn't work?" and so on. The majority of problems I see are between the X server and the drivers, because usually the wrong hardware is listed in the xf86config (now, I think many are being renamed to xorg.conf because XFRee86 did this dumb... okay, too much info... it doesn't matter right now), or people haven't successfully launched the X server, so gdm can't speak to anything via gtk.
Like, say you want to run KDE. On many systems, you may type "startx," or the really helpful ones already have a xdm/kdm/gdm or whatever already running. But let's say you are like me, you only launch a GUI when you need to. Now suppose in my xorg.conf, I have a serial mouse listed instead of the ps/2 mouse that I really have. I boot into KDE, and it may barf, or give me no mouse. That's not KDE's fault. KDE was just sending its stuff to the gtk, which spoke to the the Xorg server, and Xorg.conf thought it had a serial mouse, so when I moved my mouse, X server didn't even know it existed; it's listening to the serial port at cua00 or something. Hell-oo? It doesn't care what the hell the ps/2 port is doing, I didn't tell it to listen there. My bad. Not KDE's fault. Not even gtk's fault. Imagine if you went on a subway, and followed a defective map. If you ended up in the wrong area, is it your fault? No, it's the transit autority, who will blame the guys who made the maps. Except imagine they didn't even know the map was wrong.
Yes, the whole thing does seem like a kludge. Part of the issue with Unix and Unix derivatives is that they have a deep, rich history, kind of like an old European town. And like a European town, a lot of the stuff you see today are just add-ons to an already existing infrastructure. Have you ever seen how electricity gets to a 400 year old house? It's not pretty. There's a lot of external boxes and ugly conduits. You can't put phone wiring "in a castle wall," for instance, because you'd have to drill through stone, which is a pain in the ass, and what if you broke something while doing it? What if you needed to get to it or upgrade it later? Sometimes you can't put wiring in something because it has historical value. So a lot of old houses in these towns have boxes on the outside of the walls, and there's no place for utility poles, so the wiring is strung from building to building. And the roads? Totally not meant for modern driving. Winding one-way cobblestone streets, no sidewalks, and doors open right to traffic. People might say, "why is your town like that?" Yet most of these towns and even cities manage just fine, and in many ways, better than a modern city (especially socially).
So if you think of Unix, it comes from an era when computer equipment was large, expensive, and failed often. There's still some Linux code out there that prints out an error "printer on fire" because, well, that really did happen from time to time (now it's deprecated as an lp0 printer jam for older printers). Its whole history is based on tight control of minimal resources. That's why there are so many layers: of you don't need it, you don't use it. It stuns some people that a server doesn't need X at all! I have a few. Why have it taking up system resources if I don't even have a monitor attached to it?
Learning about X was an epiphany. I first wrestled with X when I tried to install a window manager on OpenBSD 3.1. That was HARD! I did get a serial mouse to work, eventually, even though the man pages were ambiguous and confusing (I know they are complete, but looking up how to make X work in man pages is like looking up the correct spelling of something in a dictionary). But now I think I have it all down pat.
For more detailed depth, there is a really good OnLamp essay on how this all came about here.