I'll cover all the questions even though Player3 pretty much answered them all.
-I don't understand what they mean by "scanline". Is every horizontal line a scanline?
A scanline is every 1px tall line going all the way across the screen. Literally just like the lines in the effect of the same name. That's why there's so much flicker when there's a lot of action going on, on screen. Too many sprites on a scanline will cause the game to flicker between them.
-What is a "fade region"?
I actually don't know this one, but I'll ask Overkill about it since he's worked with the NES hardware, he might post in here and help you out.
-Can a sprite have more than one palette?
Yes and no. On the NES, you're only allowed four palettes for sprites and four palettes for tiles at a single time. You can change palette's on the fly, so you're not restricted to just 4 for the whole game, but as I said, you can only use four at a single time. To answer your question, a sprite can only have one palette, however, there's a trick that, if I remember correctly, was first used in Mega Man, where they'll put a sprite over top of another sprite. For Megaman, it was his skin tone and whites for the eyes I think, that went over top of the blue body. It's a bit hard to use because then you're using more sprites on screen, but it's a wonderful trick if used right.
If you're curious about 8bit restrictions, I like to think that I know a fair share about them, since Overkill and I are working on a GameBoy Color game together. You can feel free to PM either him or I if you want some detailed answers, I'm sure we'd be able to answer almost any question you have.