First check Understanding linux desktop
I have been a Linux user for years now, but I still struggle to understand how X compares with the software used for display on Windows and Mac systems.
I know it is a client/server based software, but what is particularly puzzling for me is how it works with widget toolkits to provide a display and how these interact with each other.
I mean, take the Cocoa framework of Mac: You have GnuStep, which is an open source implementation of that framework, but (from what I can guess), it runs on X, right? Yet I suppose that Mac does not use X.
The toolkits (GTK, Qt...) generally do not interact among themselves - they are just libraries and as such (mostly) separated on a per process basis. They of course interact with the X server - by sending draw commands and reading inputs. However, some of them are not limited to a single backend (X11) - for example GTK, Qt and GNUstep have also MS Windows flavours.
The toolkits act as a unified API layer above the native drawing interface - in the case of X11 they translate request to draw a button into a series of simple objects (rectangles, shadings etc.; for example in recent GTK versions this is achieved through another abstraction layer provided by Cairo). On Windows or Mac they have the possibility to use the native API so that e.g. "GTK button" can be translated to "Windows Button", and for example on a framebuffer device it would be translated directly into the single pixels (probably again through a rastering engine like Cairo). For example Qt has about 15 various backends.
If you are talking about the desktop environments communicating with applications using different toolkits, that's a whole different story. These days, D-Bus is usually used in an X session, which allows not only GUI applications to send and receive messages to/from other applications.
Are there any alternative options to Xorg on Linux? Can I run GnuStep, for example, with something else?
One alternative (apart fom those mentioned by John Siu in his answer) might be Wayland. Yet there aren't many applications that would be able to use it natively.
Are window managers and desktop environments written specifically to work with X or can they work with other display software?
Most of the time window managers only understand the X protocol and are supposed to be run under (or above, depending from which side one looks) the X server. Pretty much because there isn't anything better (even though there are things in X11 and it's implementations, that could be better).
Ctrl+Alt+F1/2/3
is a linux thing :) OS X don't have that.