I asked my own prof this question and he said that the NSA is highly selective - something that he is not sure he could even get, if he applied. Yet, another (more senior in rank) professor that I spoke with says the NSA is one of the largest employers of algebraists and number theorists. So I seem to have two conflicting ideas.
Note that these don't necessarily conflict: there aren't many large-scale employers of algebraists and number theorists, so they don't need to have low standards to be the largest.
I have no direct experience with NSA hiring or any classified work, but I'll give an answer since I doubt any NSA employees will volunteer first-hand accounts on this site. My answer is just based on my observations of people who have applied to or been hired by NSA or contractors.
My impression is that full-time hiring at NSA is fairly selective, but not extraordinarily so. You have to be a good mathematician, but it doesn't look nearly as difficult as, say, getting a tenure-track job in a top ten department. You don't have to be particularly well-known in the mathematics community, but you'll need to beat out other good applicants for the job.
It's hard to make precise comparisons between NSA and academic hiring, because of a lack of information. When a young mathematician is hired by NSA, the outside world typically never finds out how successful they became. If a promising student is hired, we don't find out whether their promise was fulfilled; if a seemingly less promising student is hired, we never learn whether NSA identified real talents that weren't obvious in academia. The net result is that I don't believe anyone without a security clearance can do more than roughly approximate how selective NSA is.
There's also a fair amount of part-time and full-time consulting done through private companies. Some of these organizations are extremely selective, so you should not assume this is an easier way to do classified work. (In particular, my impression is that the companies that hire mathematicians are among the most selective.)
Or is the NSA highly selective and just because one has a PhD in Algebra and / or Number Theory does not mean that one can just "sign up" to work for the NSA, like signing up to join the military but with math skill sets to contribute.
Definitely not, it's not remotely like that. Just having a Ph.D. in a relevant field in no way ensures you'll be hired.