Geographic coordinate systems (lat/long) are based on a spheroidal (either truly spherical or ellipsoidal) surface that approximates the surface of the earth.  A datum typically defines the surface (ex radius for a sphere, major axis and minor axis or inverse flattening for an ellipsoid) and the position of the surface relative to the center of the earth.  An example of a datum is [NAD 1927][1], described below

    Ellipsoid 	     Semimajor axis† 	      Semiminor axis†  	Inverse flattening††
    Clarke 1866 	6378206.4 m 	         6356583.8 m 	         294.978698214

All coordinates are referenced to a datum (even if it is unknown).  If you see data in a geographic coordinate system, such as GCS_North_American_1927, it is unprojected and is in Lat/Long, and in this case, referenced to the NAD 1927 datum.  

A projection is a series of transformations which convert the location of points on a curved surface(the reference surface or datum) to locations on flat plane (ie transforms coordinates from one coordinate reference system to another).

The datum is a integral part of the projection, as projected coordinated systems are based on geographic coordinates, which are in turn referenced to a datum.  It is possible, and even common for datasets to be in the same projection, but be referenced to different datums, and therefore have different coordinate values.  For example, the State Plane coordinate systems can be referenced to either NAD83 and NAD27 datums.  The transformations from geographic to projected coordinates are the same, but as the geographic coordinates are different depending on the datum, the resulting projected coordinates will also be different.  

Also, projecting data may result in a datum conversion as well, for example, projecting NAD_1927 data to Web Mercator will require a datum shift to WGS 84.  Similarly, it is possible to convert data from one datum to another without projecting it, as with the [NGS's NADCON utility][3], which can shift coordinates from NAD27 to NAD83.

Example of a point's coordinates referenced to different datums

Coordinates referenced to NAD_1927_CGQ77

    19.048667  26.666038 Decimal Degrees
    Spheroid: Clarke_1866
    Semimajor Axis: 6378206.400000000400000000
    Semiminor Axis: 6356583.799998980900000000

Same point referenced to NAD_1983_CSRS

    19.048248  26.666876 Decimal Degrees
    Spheroid: GRS_1980
    Semimajor Axis: 6378137.000000000000000000
    Semiminor Axis: 6356752.314140356100000000


  [1]: http://en.wikipedia.org/wiki/North_American_Datum#North_American_Datum_of_1927
  [3]: http://www.ngs.noaa.gov/TOOLS/Nadcon/Nadcon.shtml