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).

History

From the bottom of the X (7) manpage -

The X Window System standard was originally developed at the Laboratory for Computer Science at the Massachusetts Institute of Technology, and all rights thereto were assigned to the X Consortium on January 1, 1994. X Consortium, Inc. closed its doors on December 31, 1996. All rights to the X Window System have been assigned to the Open Software Foundation.

From the bottom of the XFree86 (7) manpage -

XFree86 was originally based on X386 1.2 by Thomas Roell, which was contributed to the then X Consortium's X11R5 distribution by SGCS.

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.

It is probable that in the near/mid-term future, one of the FreeDesktop XServers will become the de-facto software used on Linux distributions. (See the FreeDesktop page for background on these servers).