Which programs or tools were used to create the sprites and backgrounds for 16-Bit games like those on the Super Nintendo or the Sega Genesis?
Depending on the platform we're talking about, you've got a few choices. As the best platform for editing images at the time was the Amiga with its 4096 color palette in HAM mode on OCS/ECS (Original ChipSet/Enhanced ChipSet), and even better modes if you had an AGA (Advanced Graphics Architecture) machine, I'll talk about this computer.
The best choice on that platform was the Deluxe Paint (otherwise known as DPaint), and the most popular version was probably Deluxe Paint IV, which was released in 1991 by EA. This editor had a rather limited GUI, with a very big part of the screen utilised as the canvas. It had a big amount of tools to work with such as custom brushes. Besides that, it allowed to change palettes on the go, as you needed another color. A very big feature that DPaint had, but almost no other editor had, was probably the ability to animate - it was nice, but it required a lot of RAM, and if you would want to animate on a bare 1M Amiga (not even mentioning 512K ones), I would recommend going B&W to save some memory. Using the older DPaint III is also a good idea to save some memory. Besides Amiga, DPaint was ported to Apple IIgs, MS-DOS and Atari ST, but those versions weren't that popular.
Another good editor for the Amiga was the Personal Paint, otherwise known as PPaint. It looked similar to DPaint, but lived longer (it is still available to download from the evil cloanto site). It had almost the same features, but it was expanded as the development went on for a very long time after 1995 when the last version of DPaint was released. Nowadays, this is the go-to graphics editor for classic Amiga computers. PPaint was also released on a few shareware CDs/coverdisks, of which I've got at least two. The biggest con of the PPaint is that it eats even more RAM than DPaint, thus you'll need a more expanded Amiga or limit yourself to 4-8 color images at best.
Start by not confusing 16-bits consoles and 16-bits graphics. 16-bits consoles would usually use 8-bits graphics (256 simultaneous colors) or less (96 colors, 64 colors...). 16-bit graphics would not be used on a 16-bits console (Imagine a super Nintendo managing 65000 simltaneous colors, that's crazy talk). Note: when I say "simultaneous", I mean "as opposed to all the colors available".
Therefore you can draw those with any old-school pixel-pushing program, such as the Rolls-Royce of pixel art : Deluxe Paint 1 to 4.
But drawing is only part of the problem. You need to convert the sprite and palette format to the target console format.