The program gifshuffle is used to conceal messages in GIF images by shuffling the colourmap, which leaves the image visibly unchanged. gifshuffle works with all GIF images, including those with transparency and animation, and in addition provides compression and encryption of the concealed message.
As of 21 January 2003, this site contains gifshuffle 2.0. This is the first update in nearly five years! Changes involve tweaks to a few GIF encoding characteristics, plus an improvement to the way encrypted messages are encoded. These should further reduce the chances of concealed messages being detected.
Any list of n items can be sorted n! ways, meaning that any particular ordering can represent a number in the range [0, n!-1]. This number can in turn store approximately log2(n!) bits of information. Thus, a GIF image with 256 colours can store up to 1683 bits (210 bytes) of information by shuffling the colours in its colourmap.
The gifshuffle program is public domain, and source code can be downloaded from this page. There are no patents or copyrights, so its use is unrestricted. Naturally, if you do decide to use it, the author would love to hear about it.