From "Color Management: Understanding and Using ICC Profiles", edited by Phil Green :

• Color image encoding: digital encoding of the color values for a digital image (Derived from: ISO 12231)
• Color space: geometric representation of colors in space [...] (CIE)
• Color space encoding: digital encoding of a color space, including the specification of a digital encoding method and a color space value range (ISO 12231)

Basically:

• we have colors, what we perceive with our eyes (native colors). These colors are somehow mapped into space, let's say a plane. See this chart. All the colors supposed to be on this chart (not on your monitor, because your monitor is limited to reproduce colors as well, but theoretically).
• Now, we would like to somehow describe points on this chart, points of this color space. Notice that there are infinite many points here, and we would like to use bits and bytes to describe those points (colors).
• If we could use hundreds of bits to describe the colors, we could just use the X and Y coordinates, and we would have a very good color reproduction system. However, we want to use only a few bits, maybe a few bytes to describe a color. From this, we get different approaches for color space encoding - some go for better color reproducibility, others go for smaller amount of data to be used.
• If you compare (sRGB)[http://en.wikipedia.org/wiki/SRGB_color_space] and (Adobe RGB)[http://en.wikipedia.org/wiki/Adobe_RGB_color_space] - these are two color space encodings -, you will see that the triangle on these charts is different - that triangle shows which colors can be reproduced using the encoding. This is called the gamut.
• The color space encoding not only describes the gamut, but also how fine the resolution is between color points.

Okay, so far this was about colors. There was no mention of any image, or video frame, or printed picture, etc.

So when you create a photo, your camera maps the native colors to a color space your camera uses (AdobeRGB, sRGB, ProPhoto, etc). Then, you have pixels, and those are described with bits/bytes, e.g. 3 bytes per pixel for your photo describing the color of each pixel.

Now, if we just take all the pixels as a raw image, there is no color image encoding - the image is just a representation of color points (in the color space encoding), as is.

However, if you create your photos in e.g. JPEG, there are additional transformations from the raw pixel-color data to another format. This is called image encoding, and can include color space transformation, downsampling, and all kinds of data manipulation. (For the full list for JPEG, see this page.)

So to sum this up:

• color space encoding: handles the problem of native color representation in digital format, and ends up with bits and bytes describing a color.
• color image encoding: handles the problem of having bits or bytes of color as pixels, and ends up with pixel data transformed into a more space-efficient (or whatever more usable) other format.

I hope this is clear :-).