So I don't know a lot about shaders, but I am trying to do a simple palette 'swap' and would like to use a pixel shader to do this.  The number one question I have about pixel shaders is "How does a pixel shader work?".  I believe that if I can grasp the understanding of how a pixel shader aquires the texture and how variables are assigned in a shader, I'll have a better understanding of what it is I would have to do to make a palette swap effect.  The second question I have is, how would I handle the palette data I want to 'swap' to inside the shader?
Any ideas?

I think a better place to start with this query is "How do palettes work".

For an example, an 8-bit bitmap stores up to 256 colors in an array that is used as the image's palette.
Each pixel then is a represented by a single byte that is an index into the palette array (thus storing 1 byte per pixel instead of 3 or 4).

Using a palette with textures in a pixel shader might prove to be more trouble than it's worth (I might be wrong).
In your pixel shader you will need to sample your texture (without filters, else you may get incorrect/invalid palette indices) and use that "color" value as an index into either an array you passed into the shader or another texture that acts as the palette.
AFAIK graphics cards typically store texture data as 32-bpp (possibly 24-bit sometimes) so you will not be saving any space even if you use an 8-bit. Taking the time to use the palette information will also steal time from your rendering process, so you would be better off simply using multiple textures (which are probably easier to create when you don't have to worry about keeping track of a palette).

Another option that you might like to explore is changing color values by adjusting the hue, saturation, and lightness.
You can still adjust your colors at run time within the shader by changing your HSL values. Check out Paint.NET to see what you can do with it.
More information about RGB to/from HSL can be found on Wikipedia.

Thank you for replying, it was very helpful.  I decided to stick with preloading the textures with applied palettes at load-time, seems to work fine for now.  And thanks once again.