As I understand it, they add a new set of planets with the new features, and keeping the old planets untouched.

The increased variety is not because trillions of planets are added, but because the new planets will have more varierty than the old ones.

What they really mean is there is more variety when you land on different planets, they added more variables to the procedural generation. And I gotta say it did improve over time, they have become more varied and interesting, but still with that "procedural" feel.

Unequal distribution, basically. While most planets will never be observed by a human, it turns out players congregate in certain parts of the galaxy, particularly near the galactic center. (The game starts you at a random location near the edge and there's literally a 'reach the galactic center' quest, so most players end up near the center eventually.)

So yes, there are trillions of stars, but there's only so many of them within $RADIUS of the center. In practice every planet 'near' (for some definition of 'near') the center has already been discovered and the 'good' planets are likely to already have bases. There are also spots that get their locations published in the forums or advertised in-game (good drops, cool bases, things like that) that also end up 'locally' crowded.

I found there were basically two experiences in NMS - "the outer rim" which was, frankly, lonely - you almost never encounter any signs that other players even exist and "the core" where it feels like everything has already been done - sure it's new to you, but you're never the first. Finding a middle zone where you can see evidence of other players, but there's still stuff to discover was rare in my experience.