An algorithm used to turn the curved surface of the Earth
(or another planet) into twodimensional Cartesian coordinates for representation on a map.
It is the cartographer's job to choose the projection that suits the
purpose of any one particular map. Individual map projections are
listed further down in this writeup.
The process of flattening out the Earth invariably introduces distortion
at every point of the map. There are many types of distortion, the
most common of which are

area distortion, that is, regions on a map appear bigger or smaller than
they really are,

angular distortion, meaning that the twists and turns of lines on a map
are not represented correctly.

distance distortion, meaning that distances between points are not represented
correctly.

"not looking right", meaning that the map's user cannot form a useful picture
by looking at the map.
Some projections have properties that minimize or eliminate one type of
distortion. Usually, another type of distortion is increased.

An equalarea projection eliminates area distortion but increases angular
distortion.

A conformal projection eliminates angular distortion but increases area
distortion (and objects often don't "look right" anyway).

An equidistant projection represents all distances from one point or
linear feature correctly.

A compromise projection trades off between area and angular distortion
for the purpose of "looking right".
Because of this, individual map projections are useful only for certain
types of maps. It is the cartographer's job to decide which types
of distortion thwart the purpose of a map and which types do not, and choose
a projection that suits that decision.
Some map projections can be constructed geometrically. Ancient cartographers
invariably used one of these projections. As history passed, however,
the number of purposes for maps multiplied, and geometricallyconstructible
projections couldn't serve all of those purposes. As mathematics
and science progressed, it became possible to describe map projection algorithms
mathematically. Nowadays, there are more projections that come from
mathematical formulae than geometrically constructible ones. Many
of these newer projections are named after the first person to describe
them. A few of them are completely useless, but are well known because
of the people who promoted them as a pet project, as selfaggrandizement,
or as propaganda.
Every map projection has formulae which can be used to convert angular coordinates of points on the Earth's surface (latitude
and longitude) into rectangular Cartesian coordinates.
However using the formulae for a particular map projection requires
that the latitudes and longitudes of individual points be as accurate as
possible. This requires a model of the planet's surface, called a
datum. Of course, datums introduce their own special kinds of distortion,
and the cartographer must choose a datum to suit the purpose of the map
being made. For a world map that is hung on a wall, a sphere is more than
sufficient.
Sometimes, a particular choice of datum (e.g. using a sphere) will simplify
the formulae being used. Other times, it will complicate the formulae,
requiring the use of an infinite series to approximate a final coordinate.
The cartographer must decide which point of the earth's surface to use
as the "pole" for the projection, that is the point from which latitudes
and longitudes are measured. Although the projections for most maps
are calculated using either the North Pole or the South Pole, it is theoretically
possible to choose any point on the Earth's surface and call it the "pole".

A polar projection uses either the North Pole or the South Pole.

A transverse projection uses a point on the Equator.

Any other projection is called an oblique projection.
However, the shape of the earth introduced via a datum makes creating oblique
projections horribly complicated. (When projections are calculated
using a computer, "complicated" means "a potential source of error").
Some projections introduce one or two "standard lines", circles on the
Earth's surface that are represented correctly. (In a polar projection,
these are parallels of latitude, and are called "standard parallels").
As points get farther and farther from these standard lines, the projection's
distortion gets worse and worse. This, however, makes the choice
of a pole easier: If the area to be mapped is longer easttowest than
it is northtosouth, a polar (usually conic) projection is the best.
If the area to be mapped is longer northtosouth than it is easttowest,
a transverse (usually Mercator) projection is best.
Some European countries use "modified" versions of the projections below
for their national mapping systems.
Traditional developed map projections (follow the link for a general
discussion):

EqualArea projections:

Conformal projections:

Equidistant projections:

Other useful azimuthal projections:

Other cylindrical projections:
Pseudoconically developed projections:

Pseudocylindrical projections:

Pseudoconic projections:

Pseudoazimuthal projections:
Multipart (aka "Multisuperficial") projections:
Sources:
More cartography classes than you would care to contemplate
However, the best source for anything you want to know about map projections
is
Map Projections: A Working Manual
John P. Snyder
U.S. Geological Survey Professional Paper 1395
United States Government Printing Office, Washington, 1987
Elements of Cartography, Arthur H. Robinson et al., has a nice
chapter or two on map projections.