From what I have read, the prefix used to be NX* in the NeXTSTEP days and was changed to NS* around the time OpenStep came on the scene.
Actually, I believe the actual prefix of NS originally meant Next/Sun whe Next was working with Sun Microsystems. But, who knows? We need one of the original developers to help clear this up.