The userland GUI stack begins with the Xorg server, which manages hardware -- both the display and input devices -- and provides the foundations of a windowing environment. It is a server whose clients are GUI applications that appear in a window. I believe the name was originally derived from one of the X shaped cursors (but treat that as apocraphal, see vonbrand's comment below); the earliest versions of a Unix based X Window server date back to about the same time as the orignal Microsoft Windows and Macintosh systems. You can run X all on its own, but you need to configure it to start some applications or else you are left with an empty screen and a mouse manoeuvrable X. Not so interesting.
Xorg is common to most general purpose linux distributions, though there are some (bleeding edge) alternatives available. The next layer in the stack is the Window Manager (WM), at which point linux becomes heterogeneous -- there are a wide variety of window managers available. Their primary purpose is to provide a unified interface to Xorg for the user; they are responsible for titlebars, borders, and arranging and controlling (maximize, minimize, iconify, etc.) all the windows on the desktop. They may also include specialized applications of their own, such as taskbars, and provide application independent menus. Many, but not all, window managers can be used on their own as together with X they provide the essentials elements of what most people would consider a graphical desktop.
About 15 years ago a third layer began to appear, the Desktop Environment (DE). These built on the more fanciful aspects of window managers and provide various kinds of integrated services. They have as their centrepiece a suite of applications including a file browser and GUI terminal -- previous to this, these existed only as independent entities. DE's usually use stripped down and simplified window managers which are responsible strictly for window decoration and management (i.e., they build upon a clear delineation of responsiblities).
With regard to mixing and matching applications associated with specific DE's, it is usually possible. GNOME is tied into a larger infrastructure parts of which are very commonly used by linux applications, so your system will inevitably have bits and pieces of GNOME related software running regardless of what WM and DE you use.