The palette can be about the hardest and most daunting part of creating an MS Agent character, and is probably the main reason that not very many people create MS Agent characters, they typically give up or quit creating characters after doing several of them, they feel it's just too tedious and time consuming.
The key is in choosing an appropriate color for the background which will be transparent. It can be just about any color you wish, but it's important that none of the character or prop colors be remotely close to the transparent background color you've chosen to use, or you can run into a multitude of problems.
There's many factors that must be considered in choosing the correct transparency color for your project. For example, the higher the resolution and color complexity of the character you're rendering, the harder it will be to choose the right transparency color and create a quality palette where the character has relatively smooth edges. It really requires proper pre-planning before you even start creating and rendering a character.
The palette creation and batching can all be done in most good paint programs such as Corel or Photoshop.
The max number of colors that can used in a GIF is 256, but your palette doesn't necessarily have to include that many, it can be any number of colors up to 256.
It's a very complex process especially if you're wanting to try and create MS Agent characters from high resolution Poser characters.
I'm sure you were hoping for a simple tutorial or a reference to some special palette tool that would make the process relatively easy. Unfortunately, that's just not the case. We were probably the first to create an MS Agent character using Poser nearly 13 years ago, and it took us a along time to master the techniques we use. Even though we now can almost create a character in our sleep, it still typically takes us well over 100 man hours to develop a character. No matter how good you get at creating characters, it's still a tedious time consuming process.