An X Server is a program that is responsible for drawing graphics on a machine's video.
Graphical applications (called "X Clients") use the X11 protocol to talk to the X Server. This turns around the usual meaning of client and server, and the application may be running on a remote machine, and displaying on your local machine.
On Linux platforms, the X11 implementation most commonly used is the XOrg reference implementation. (Previous versions of distributions used the older XFree86 implementation that XOrg is derived from).
When the Open Group changed the licence of their X11R6.4 release to be non-Free in 1998, the XFree86 project kept their own fork under the more liberal license, and had much more active developer support. (See this debian-devel post). Also, RMS talks about this in his essay on CopyLeft vs non-CopyLeft (but still free) licenses at http://www.fsf.org/philosophy/x.html. The XFree86 implementation of the X11 protocol is the one that survived.
In 2004, the XFree86 leadership announced a change to their license, introducing the documentation/advertising clause of the old-style BSDLicense (now removed from BSD software) to their upcoming XFree86 4.4 release. Because this is interpreted to be incompatible with GPL'd software, the major Linux distributions are migrating to Xorg
OS News has a good summary.