A color map is a pseudocolor look up table. It takes a single valued image, like a gray scale image or indexed image, and uses the value (gray level) to assign a color to it such that those pixels with that gray level show up in the specified color.
A color space is a 3-Dimensional coordinate system where you can plot a pixel's color as a point in that space. For example in RGB space, you could put a dot at every location where that particular value of red, green, and blue appears. There are other color spaces that better correspond to human vision, such as HSV and LAB color spaces, and they are often easier to use when finding certain colors in an image, as demonstrated by the tutorials in my File Exchange
