Back then you'd typically use an 8-bit display mode, so your actual display is paletted to begin with. You have a single global palette for all objects, but select objects have what you might call a "colormap", which is another intermediate table that maps a palette entry to it's final value.

So there are two levels of lookup: first you take an input value of 0..255, look that up in the colormap giving another 0..255 value, which is the final palette entry that's used. That way you get to switch colours without needing to load a new palette for your display mode (which can be expensive). Objects that don't need to be colormapped can just use the input value directly so they avoid the extra lookup and be drawn faster.

This is all done using software rendering, of course.

For a modern emulation you'd use a texture read: using an 8-bit luminance-only texture, you look that up in a 256x1 texture to get the final colour. To switch colours you just change the 256x1 texture. That needs a shader, of course.

More fully-featured recoloring support is generally done via a mask texture and layering. Each object as a base color texture. It then has an additional one-channel texture with white (1.0) meaning "recolor this texel" and black (0.0) meaning "don't recolor." Values between the two extremes can be used for "partial" recoloring. The base texture should have either black texels or white texels in any location being recolor (depending on whether you use multiplicative or additive recoloring). You can have a base color in this location if you wish for that color to be combined with the new color.

Your shader then samples both the base color and mask textures. It has a color value as input, either as a uniform or per-instance variable. The code would be something like the following totally untested HLSL:

// inputs
Texture2D texColor;
Texture2D texMask;
SamplerState sampler;

float4 ps_main(float2 uv : TEXCOORD0, float4 recolor : COLOR0) : SV_TARGET
{
  float4 color = Sample(texColor, sampler, uv);
  float4 mask = Sample(texMask, sampler, uv);

  // additive
  return color + mask * recolor;

  // multiplicative
  return color * mask * recolor;
}

Which of additive or multiplicate you want to use is totally up to the look you're trying to achieve. Neither one is innately better than the other; they simply give different results when you want to mix new colors with old colors (e.g. to have a part of a model that always has a green tint but is still recolored).

You can use multiple masks (possibly encoded as multiple channels in a single mask texture) and input colors if you want to allow recoloring different parts of the model to different colors.

The shader code sample above recolours with a single arbitrary colour, but a similar approach can be used with proper palettes (constraining the colour swaps in exchange for changing multiple colours in a coordinated fashion, see Street Fighter II, III, IV characters for pretty examples).

All palettes can be consolidated into a single RGB or RGBA 2D texture (e.g. colour index across u, with different palettes stacked as rows along v); then you could look it up (nearest neighbour) with u coming from a single 1-channel sprite texture (also nearest neighbour) and v interpolated from vertex data (identical for all vertices of each sprite, and as a consequence for all fragments of the sprite).
Note that these palettes would cover one sprite only (or a set of related sprites, such as animation frames or separate pieces of the same entity), not the aggregate of all graphics you use: different sprites could use the same colour index with a different meaning, even if sprites are consolidated into texture arrays and/or large texture atlases.