A color-space is a basically all possible colors within a certain bounded bounded volume. There are numerous color-spaces and they are usually defined by a set of variables. sRGB for example is all colors possible by linear combinations of its 3 color-primaries.

A color-gamut normally refers to all possible color that a monitor can display. These are very similar to a color-space except that a color-space is conceptual but color-gamut is practical. It is the limit of what was achieved when constructing a display. More times there is a huge overlap but there could be areas of a color-space not covered by gamut and vice-versa. The ratio of color-space to gamut is known as coverage. You often see a good monitor state 98% coverage but you can also see some that say 108% of sRGB (for example), meaning their gamut is larger than the color-space.

Color-Depth is the granularity of colors with the color-gamut that defines the limits of what a screen can display. All screens have a certain gamut, whether specified by the manufacturer or not. Digital displays also have their own bit-depth which is sometimes different than the color-depth rendered by the operating system.

Color-depth is essentially precision. It is like measuring the distance between two points and stating it as 102km while it could also be measured in meters which would result in a more precise distance, it could be 102,207m. Color-depth is necessary because computers produce images digitally. Even on analog displays where the display had no color-depth, the operating system or at least application had to output its signal at a certain color-depth. The graphics cards back then had DAC (Digital-to-Analog Converters) that turn a signal of a certain bit-depth into an analog wave. Analog monitors themselves though could be driven at any precision and although desktop computers usually output 6-8bps, there were more powerful computers that used 12-bpp on the same displays.

Paletted colors as you call them are another variant of this. The common term is Indexed Color which will make sense in a moment but let's break it down first:

• Most computer displays are made of a backlight and a liquid crystal panel where each sub-pixel can vary the amount of light that passed through it. The interface to the panel is digital and sets the maximum bit-depth of the screen. Most modern screens use 8-bits per sub-pixel but there exists 6-bit ones which were common in laptops plus 10, 12 and 14 bit ones at least.

• When you set the bit-depth of the operating system, you are defining how colors are specified in software but the operating system translates it to the color-depth of your display. Displays can do that internally too and high-end monitors often do that to improve accuracy. So while 24-bit color (8-bits per channel) may be selected in the operating system, a monitor can translate this into 14-bits using a Look-Up-Table set by a calibration device. Many panels with only 6-bit depth allow the OS to address them as 8-bit but they drop the lower two bits.

• A Look-Up-Table (LUT) translates input colors received by the operating system into colors that are sent to the display panel. This translation can happen inside the monitor or in the graphics card. Implementations differ but generally these LUTs are interpolated and do not actually specify a mapping from every possible input color.

• Indexed Color is a simplification of this designed to reduce memory usage. The depth-of-the-palette defines how many entries it has. So a 4-bit color palette can address 16 colors. Usually a program starts by setting the palette which defines a color to output for each possible 4-bit number. Then when a color is specified, it is the index in the palette that is used and the displayed color is the value stored in the palette.

Possibly the most common indexed color are GIF images. Each pixel in an image can be one of 256 colors but every image can use a different set of 256 colors from 16 million. So, while you can evenly distribute colors of a palette across a color-gamut, that is rarely the case.