Your understanding of the difficulty (re: fading in/out) on the NES is correct -- it has to do with the extremely limited (effectively) pre-defined palette and choices.
The biggest complexity, IMO, lies in deciding *visually* what looks good fade-wise. Let's talk about that. It's a highly subjective topic.
For "simple/dumb" fades, the NES palette colours are positioned in such a way where you can add/subtract $10 from the palette value to get a darker or lower shade... with two caveats: i) avoiding $0D (do not use this value!), and i) transitioning from the "darkest colour value" to $0F (total black). It also operates mostly on the concept that you will always be fading from brightest to darkest/black, or from darkest/black to brightest. Obviously you can tweak the code to limit the range, but... well... just keep reading.
This method is easy/dumb because you can do it in software. It's identical to what Kasumi demonstrates in that post. It works great for most things, but that's again subjective.
The more complex fading method doesn't involve simple +/- $10 math, it involves lookup tables for each "step" or "stage" of a fade. This is what a lot of games do; it's a pre-calculated table of each "phase" going from colour X to colour Y. Sometimes it's 4-phase, other times 5 or 6. To understand the model, you need to look at the palette closely and notice several things:
1. There are LOTS of choices when going from white to black or black to white. For example, white to black could be: $30 -> $20 -> $3D (or $10?) -> $00 -> $2D -> $0F. Do you need all those "phases"?
2. There are substantially less choices when going from a colour to black, or from a colour to the brightest colour. For example, let's take blue. It could be $01 -> $11 -> $21 -> $31. But maybe visually that doesn't look good, it's only a few "phases". What might look better is (I'm just making this up BTW) $01 -> $0C -> $11 -> $21 -> $2C -> $31.
The tricky part about #2 is that you have to remember 2 additional things:
i) Not everyone's TVs are going to have the same tint and hue. So a blue transition that uses some cyan as "intermediates" to help potentially make it look better might look like crap to some,
ii) The complication of how pixels of different colours look on actual TVs when placed next to one another. Ex. that red pixel next to a brown pixel visually looks very different/unique (almost its own shade). Really good NES art tends to cater to this; you load the game up on an emulator and you're like "wow, it looks so... sterile. Clinical. Plain. Literal." Load it up on a NES hooked up via A/V or RF and it's like "ah yeah the colours sort of bleed together". So you get to think about how that affects fades as well. IIRC, the games Magician and Faxanadu use this a lot.
If you want examples of what good fades look like, and this is again subjective, load up Ninja Gaiden. Entering the first bosses room there's a fade, after killing him another, and when loading into the next level another. Load this up on a NES and look at it. Then load it up on an emulator like Nestopia using the stock palette and look at it -- on some transitions a dark colour goes "too bright" for a phase, followed by it "darkening" for the next phase. Notice how different "parts" of the screen seem to take longer to fade in/out than others -- it's a effect of the palette transition choices Tecmos made. If you just want to see it yourself, here are two videos of gameplay from Youtube:
https://www.youtube.com/watch?v=ueeKMQSS4bw (emulator with dumb rounding/smoothing filter applied)
https://www.youtube.com/watch?v=uzU53dVHGSo (actual NES)
The text fade I did in the FF2j/e intro replacement for Neo Demiforce was really easy: it was a single colour in the palette I had to deal with: white to black and black to white. I opted for $0F (black) --> $00 (grey) --> $10 (lighter grey) --> $20 (even lighter) --> $30 (white). Fading out was the exact opposite. Delays (for smoothness/speed of the fade) were done by simply waiting for VBlank. I thought about trying to fade in/out the logo too (on reset, and when starting), but when I started thinking about all of the above, I opted to just do text only. I think the 3 or 4-stage "simple" way looks best visually, barring maybe an exception for black-to-white and white-to-black which could involve one or two more steps -- but it means more code, and other graphics on screen (of other colour) have to "wait" for a phase without any change (again, see Ninja Gaiden).
Edit: lots of other replies above me that say basically the same thing. Seems we're pretty much all in agreement ;)