GIF images use what is known as an indexed colour scheme, instead of each pixel being stored as three bytes (one for each of red, green, blue), each pixel is stored as 1 byte. The value of this byte is used as an index into a table of fixed colours. Since there are 256 possible states for one byte, the table has at most 256 entries and therefore a GIF image can at most be made up out 256 different colours.
One consequence of indexed colour is that the appearance of an image can be changed without changing the values in the pixels but by just changing the colours in the colour table. By doing this in clever ways it is possible to achieve some interesting effects, some of these will be discussed here.
As an initial example consider the following image on the left, it should appear entirely green. On the right is a grid of 256 colours representing the colour index table. In this case index 0 is white, index 1 and 2 are green, and the remaining indices are all black (they aren't used in the image).
We are free to change the values in the colour table at will. For example if we change the colour for index 1 to blue, then all the pixels in the image that refer to index 1 will immediately change their colour. The resulting colour table is shown below on the right, the resulting image is shown on the left. Note that the image data on the left above and below are identical, only the colour table has been changed. If you have appropriate image editing software you can download the apparently total green image above and change the first colour index to whatever colour you wish, making the hidden message visible.
Of course this didn't happen by magic, this image was specially created by creating a coloured background and writing the text on it in a different colour. The index (1 in this case) for the text was then set to the same colour (green in this case) a the background.
While potentially tedious if done by hand, this technique is not limited to simple images as shown above. Any picture represented as a GIF image can have a message encoded into it as long as there are enough spare entries in the colour table. In general you need an image that only uses half it's colour table entries, the other half can be used to encode anything, even a whole different image.
In the past this technique was a common way to achieve special effects, the technique was known as index colour animation. To achieve animation effects with minimal processing, specially designed images would have their colour tables varied yielding the appropriate animation. The more expensive alternative for a 24 bit image is to modify every pixel, colour table animation only required the much smaller colour table to be changed.
Consider the image below on the left and its associated colour palette on the right. The palette consist of just 9 values, although white isn't actually used (most gif software insist on at least a white and black entry in the colour palette).
By changing the palette at each time step, annoying little animation like the following could be created. Of course with a skilled hand more pleasant colour table animations were used to create opening flowers, waterfalls, bouncing balls, scrolling text, etc.
Please note that the animation above is NOT represented here using colour table animation but rather as an animated gif in order to convey the principle. Colour table animation is generally reserved for what are now considered old graphics systems that were inherently indexed colour. Colour animation was achieved by changing the system colour palette, the result would appear as shown in the image above.