How do KDE applications run under Gnome?
Both GTK and Qt are toolkits for building graphical interfaces. Each UI toolkit provides its own functions for programs to create widgets (buttons, textboxes...) and comes in the form of libraries that the graphical program links against. A program written for GNOME will use GTK (libgdk and libgtk), while KDE programs use Qt (libQtCore and libQtGui), Enlightenment programs use EFL, and so on.
However, all these toolkits use the same X window system & the same X11 protocol. To make things appear on screen, the toolkit connects to the running X server (usually Xorg, previously called XFree86), sends X11 commands (create window, draw something in a window), and receives X11 input events (mouse, keyboard, window resize, &c) back.
(Most modern toolkits, like GTK, Qt, or EFL, perform fancy drawing themselves, and just use X11 to send the finished image of the whole window, and the X server merely puts it on screen. Older toolkits like lXaw or Motif instead use X11 to draw primitives like lines or rectangles or text, and the X server does all rendering.)
The X server then does the job of putting everything together, talking to your graphics card, and so on. This way, you can run programs that use various different versions of different toolkits, because in the end they just use the same OS facilities.
Mechanism, not policy
The multiple-toolkit situation is not unique to X – for example, you'll find Windows programs using the standard comctl32 but also WPF, .NET WinForms, Chrome's Aura, Firefox's XUL, and even the same GTK or Qt. Most games use their own styled controls. Really, this is possible on any graphics system that lets you draw an image across the whole window.
However, one of the principles of X was "mechanism, not policy". This means that the X server only provides the mechanism for its clients (graphical programs) to do various things, but imposes as few rules as necessary. In other words, X takes this to greater extent than any other graphics system.
For example, one of the integral parts of a graphics system is window management – the drawing of frames (aka decorations) around each window, the ability to move & resize windows, and so on. Windows and OS X have a window manager built into the system, but in X it runs as a separate program – the X.Org suite comes with a minimal twm, but almost all desktop environments ship their own window managers (GNOME had Sawfish, Metacity, gnome-shell; KDE has KWin) providing integration with the respective desktop environment.
(Like toolkits, modern "compositing" window managers actually take over Xorg's job of composing all windows onto the final screen image, allowing things like shadows or effects to be added.)
With modern desktop environments, this has actually created problems as well. To use the most common example: the same "grab keyboard" functionality is used by hotkeys; pop-up menus; and screensavers, and only one program can use it at once. This means you cannot lock the screen while a pop-up menu is open, or skip songs while the screen is locked. It is one of the several reasons Wayland is being created as the replacement for X11.
Side note
Technically, this even means you could run X programs on a different computer, talking to the X server on your machine over the network. Indeed, this was the primary use case in the early days, and it is where the name "X server" comes from in the first place. It is possible to run an X server on a Mac and have it display windows created by programs running on Linux, FreeBSD, even OpenVMS.
However, as mentioned above, modern toolkits perform all drawing client-side (fancy graphics and pretty fonts are quite hard to do with X11 primitives), and only push the final images to the X server, which is very fast locally, but requires a fair bit of network bandwidth.
(Other protocols, like RFB (aka VNC) or Microsoft's "Remote Desktop", are designed for this, and they have very efficient ways of compressing the window images.)
Part of the answer is that the leading desktop environments (Gnome, KDE, XFCE, perhaps others) work together under http://freedesktop.org to make such interoperation possible. One of the specifications published by FD.o is EWMH, which ensures a certain level of compatibility between window managers (for modern features, not just basic window management).