Index painting occurs on programs that have more advanced modes of painting than MS paint or something. There are so called 'dirty' tools. Not dirty as in ethically, but as in 'creating uncontrollable smudge'.
The large degree of mystification concerning this issue is due to that most people only use MSpaint to pixel (and some in fact erroneously have defined pixel art to only occur when using MSpaint) but also due that that the people who index paint in this day and age really do not want to explain what it is to people, because once they understand how it's done, they won't seem as awesome as they want to seem. This is a demoscene disease.
What index painting is:
Instead of a small controlled palette, the artist starts out by making huge 16 or 32 color ramps (you'll notice most index painted work has straight ramps. Ask if you don't know what I mean with 'straight ramps') of various hues. He then proceeds to draw as if you'd draw in photoshop, using blend modes, smudges, auto aa-ing and so on. Essentially in Deluxe Paint, Personal Paint, Brilliance (all amiga stuff) or Gfx2 or Pro Motion for the PC, you can treat an image like you'd do in photoshop more or less. You don't have to work pixel-specific as most pixel artists do.
So let's say that you've arrived at an image that was made using soft brushes, auto-aa, blend modes, so on. The computer has done most of the work for you. You have what looks like an oddly colored small resolution photoshop image. If someone posted this on Pixel Joint, everybody would clearly understand what the difference between handpixelling and index painting is. Most index painters however at this stage go in on the pixel level and start refining the image. It's essentially closer to what you'd do if you scanned in a watercolor image, color reduced and then zoomed in and dithered around and stuff, sharpening a bit here and there, simplyfying here and there than it is to straight-up pixelling.
So the end result is an image that has the volumetric control offered by dirty tools, but the finish of pixel art. This is index painting, and it's a valid way to work as long as you don't claim lies about your process. However a lot of these people do, and they make an argument from old-schoolness (*I* have an amiga and deluxe paint noob, so what I do is real pixelling and you don't have to understand it, just love me for it!) and they actively obfuscate their means. Why? Because next to someone's MSpaint doodle, the index painted image (though it may lack in various fundamentals like light, anatomy and structure) looks 'awesome'. Most index painters have the demoscene mentality, and WINNING over their peers is the main motivation for creating their art. They take the demoparty mentality (where images are voted on and someone wins the gfx compo) to gallery sites like Pixel Joint and they revel in the internet ass-pattery.
I hope you see things clearly now.