I hope a more technical post will be appreciated. If not, I'll head back into lurk mode. The NES stuff always pulls me out.

I also apologize if I compared to other games too much, but I thought it might help understanding.
Just a few corrections here to start:
The cart (probably Konami-designed) has modifications to increase memory size to fit in more sprite and tile data. Effectively this means that this game couldn't have come out as an NES launch title or anything of the type. Keep this in mind if you think 'huh the NES came a long way since super mario and other simple looking arcade ports to this'. The artists came a long way but also, the cart configurations changed. I'm sure we have some actual NES cartridge wizards in the forum that could more assuredly talk about their specs.
Well, I can try. Shatterhand is an
MMC3 game. MMC3 and the other MMC series were Nintendo developed as far as I know. This means Shatterhand doesn't have any more of a complicated cart than 1988's Super Mario Bros. 3, and in fact uses less space for code/data/levels, probably to save money since ROM was expensive. (Both games use 128 KB for graphics, but SMB3 uses 256 KB for code/data where Shatterhand only uses 128KB for that. But... I suppose that's not useful info for this discussion) Therefore you can chalk a lot of Shatterhand's graphical victories to its artists, rather than its cart.
It's all about color usage and tile busyness I think. It takes a page from the Batman game, the black color is the universal color here that ties almost every tile together and frees up the other two colors per tile to be whatever else since black can dither into anything for an extra darker shade and unifies.
Three. If black is the universal color in all background tiles, then each tile palette still has three other colors to choose from. There are four background palettes that have: black, and three other colors. It's sprites that only get three colors since the universal color used for all sprite palettes just becomes transparent instead when the sprite is drawn.
Don't be afraid of complicated tile configurations either, you have (imaginary) cartridge space.
In fact, this game could have used twice as much space as it did for tile/sprite data. It just would have been more expensive to produce.
On the whole "parallax scroll debate"
The splitscreen parallax:
I assume they scroll the screen during scanline interrupts?
Is it possible to scroll one part to the left, the other to the right?
Sprites are always layered afterwards?
Yes!
Yes! See Megaman 3 (another MMC3 game.) Press start on the title screen and watch the top and bottom parts of the screen scroll in from the left, and the middle scroll in from the right to make up the robot master select screen.
Not necessarily. ptoing went over the basics of that.
The best "parallax scrolling" I've seen is in
Battletoads. (Note: Battletoads is NOT MMC3 but...) One of the features MMC3 adds is a scanline counter. This allows different vertical portions of the screen to have different horizontal scroll values. (Split screen scrolling as described in Megaman 3 above) On the title screen of Shatterhand don't press start. Eventually you'll see an enemy shooting, and a guy will pan in from the right blocking the bullets with his arm. That's an example of this. It's not exactly as wonderful as parallax scrolling with different background layers though.
But actually split screen scrolling can be used in carts with no special configuration. See Super Mario Bros. where the level scrolls but the HUD (score, world etc) doesn't. MMC3 just made that kinda thing MUCH easier since you didn't have to wait in idle loops to change the scroll value mid screen. You could rely on an interrupts. I can't even guarentee at this point if that scene is done the MMC3 way or the SMB way without looking at how it's running through a debugger, but "easy" split screen is a fun feature of MMC3.
I might make a more detailed post regarding what this game does with its graphics codewise during gameplay, as well.
Edit: Or not. A quick run through shows it barely does anything neat. Doh. Ptoing covered that.