How does X11 work?

"If I recall correctly ssh -X maps the X server to the target machine and then routes connections through the channel created by SSH to the terminal (i.e. your machine). The ""X server"" is the software that draws the window for the ""X clients"" which are the programs that use those windows.
Yes, startx starts the X server. But on Mac OS X you start the X server by starting X11.app in Utilities.
You wouldn't really want that unless you are trying to restart the X server on the computer you SSH into. But that wouldn't have anything to do with your connection to that computer or the programs you want to run via that connection.
Not sure I understand the question. What window manager the remote server runs is inconsequential for your connection. Window managers run on X servers (they are special X clients) and the X server on your Mac and the X server on the remote machine are two separate beasts.
VNC is a different solution for the problem of displaying GUI apps remotely. You can combine the two but I recommend you try to understand them separately.
Let Paul be your Mac and Peter be the (Linux) machine you connect to:

Paul: startx (or rather, start X11.app and use the terminal window it creates for the following)

Paul: xhost +Peter

Paul: ssh -X Peter

Peter: xlogo& (this should now display on Paul's screen, if not, continue)

Peter: export DISPLAY=Paul:0

Peter: xlogo& (this should now display on Paul's screen)"

"How does something like VNC play into
all of this? Is there a difference
between a remote X session and just
sshing into the remote machine and
using startx?

VNC does a similar job in a slightly different way. VNC simply takes an entire screen or a single window and sends the video over the net to a VNC app your local machine. X runs an application on the remote machine but sends all the display commands over the net to your local X display. X actually does this even when running locally but a network call to the same machine can be shortcutted and is very quick.

ps. You don't ssh into a remote machine and startx - you start the X server locally then ssh into a remote machine and start an X application (office/gimp/xeyes/etc) and X handles it appearing locally."