Its a fairly interesting question -- more interesting than just colors anyway.
The trick to making a game that has that nostalgic 8-bit feeling, really, is to be very true, or mostly true to the whole experience. For most people in North America, and many in Europe and Japan, the 8bit era was defined by the NES/Famicom, and so the answer really is "Do as the NES does" if you want to evoke the feeling of the authentic 8-bit experience in those people. In other parts of the world, the Sega Master System, which was in all ways technically superior to the NES, either dominated or made a more-even showing against the NES/Famicom -- In Central and South America, it thrived well into the SNES/Genesis Era (There are ports of street fighter 2, mortal combat, and Sonic 2, for instance, owing partly to the GameGear being essentially a portable Master System), and it made a stronger showing in Europe than it did in North America. For those people, the Master System defines the 8-bit experience.
But its not just the colors of pixels that makes the systems feel like they do -- its also the other limitations that game developers had to work around. If you don't follow through on those, your game might feel less like a 8-bit game, and more like a modern game with bad graphics and animation. For example, the NES only had memory for 64 sprite positions on the screen, and you could only have 10 of them on any given scanline of the screen. Sprites could only be 8x16 at the largest, too, so larger sprites (think Battletoads, or TMNT: The Arcade Game) consumed several hardware sprites -- when the bad guys flicker in an NES game, or the game slows to half-speed, its because of those limitations. Another limitation on the NES was that any given hardware sprite could only contain 3 colors + transparency. In the background graphics, something similar is true -- only 3 unique colors + 1 shared background color, and also all background tiles were 8x8 pixels, and the 3 unique colors were shared by every 2x2 group of such tiles. Similarly, most NES games didn't have very smooth animation because of limitations on how much graphics memory was available. Put all of these things together with the NES palette, and you will have a game that feels very much like an NES game.
But, you don't have to be totally accurate, either, there's no good technical reason today to have flicker or slow-down, so don't unless you have a design reason for it -- but, you also can't use that new-found freedom to make a game with 100s of sprites if you still want it to feel like an authentic retro game. Or, you might not care, or you might like to make a game that's a sort of unconstrained imagining of what 8-bit games could have been. Similarly, the NES color palette itself isn't perfect -- There's no good beige, no good dark red or purple, no vibrant orange. The guys who made Shovel-Knight took great pains to be authentic, going so far as to implement color-cycling in a modern GPU shader, but also added some of these colors I mentioned to their palette.
Let me end with a few resources:
Breaking the NES for Shovel Knight
