There are two key points to generating good looking 256-color images: Choosing a proper palette and obscuring color errors (usually by some kind of dithering).
If you want to display only a single image at a time, you can create a palette adapted to that image. Properly choosing the palette color immensely reduces the amount of color errors you had to conceal.
In case you want to display multiple arbitrary images at a time, you can not optimize the palette to specific images, but you would need to settle on a common palette for all images.
There are two fast ways for down-converting high color images: Just choose the nearest palette color (creates awful banding) and dithering with a regular pattern derived from the low bit(s) of the X/Y coordinate values (generates annoying patterns). There are more advanced dithering methods that create more pleasing results, but they are noticeably slower. The primary concept for appealing dithering result is error diffusion, and the Floyd-Steinberg algorithm is a common realization of that idea.
Even in case you need to choose a general purpose fixed palette, you can optimize the palette for having their colors chosen for approximately equal visual difference (more shades of green than shades of blue, more bright colors than dark colors), or for equal spacing of the RGB values. The former choice allows way better pictures, but requires slow algorithms for color mapping (in case of 16bpp->8bpp, you can cache that mapping in a lookup table), often resorting to brute force searching. The latter one makes finding the appropriate color index from the high-color RGB values and dithering correctly more easy.
If there are no needs for superior quality, you go with a fixed numerically generated palette (commonly 6 shades of each red, green and blue, the "web-safe palette" or 8 shades of both red and green combined with 4 shades of blue), and you apply no dithering or very simple regular dithering algorithms (like "round up the odd pixels, round down the even pixels"). This approach is easy and creates the "run-of-the-mill 8-bit pictures" we know today. Anything better requires more effort and is thus more expensive to create. Good quality 8-bit pictures is no goal commercial vendors of today want to spend resources (money, time, know-how) on. Customers just are expected to run high-color or true color video modes.
On the other hand, in the late 90s, picture quality of an encyclopedia like encarta was a major selling point, and graphics card with insufficient video memory and bus bandwidth for making high-color modes useful general-purpose modes were still common, so the big vendors spent considerable resources on generating quality 8-bit images.
Just as a commenter said in the comments: Software like GIMP still have a dedicated "convert to indexed" function that allows choosing the methods used. The choice has a major influence on processing time and image quality. "Save as 8-bit" in software like MS paint likely uses the most simple approach possible, though.