What does "frozen" mean (e.g. for catcodes)?

Clearly the concept isn't limited to catcodes either

In all cases except that last one that you link to, "frozen" isn't being used to refer to any technical term referring to a specific definition it is just being used in colloquial English language sense to mean "unchanging".

Catcodes affect the interpretation of characters in the file as they are parsed to generate character tokens which are used by the rest of the macro system. The important thing is that a character token holds both the character code and the cat(egory) code and does not change if the catcode values are changed.

So for example you can do

 .... {\catcode`\&=12 ... & ... } ...

and typeset a normal &

but

 .... \textbf{\catcode`\&=12 ... & ... } ...

will fail as the argument of \textbf will have been parsed first so & will have been read from the file with its normal catcode making it an alignment separator, so when the character token for & is seen as the text is typeset it will generate an error even though the current value of the catcode settings for & at that point has the catcode as 12.

Rather than technical discussion about tokens it is easier to tell people that catcodes are unchanged (or "frozen") once read, which is why \verb and similar commands do not work in the argument of another command.

The word frozen is almost always used in a figurative meaning for something that has been saved in a fixed and unmodifiable way (unless somehow unfrozen).

“TeX: the program” (essentially what you get with texdoc tex) uses “frozen” in a very technical meaning. There are some internal control sequences that aren't accessible from the user and cannot be redefined. A common one is the “frozen \relax”.

Another common meaning of frozen is for programs that are no longer developed (but perhaps maintained). This is the case of TeX 3.

I'll only mention the references to the TeXbook and babel, adding some for LaTeX.

The passage in the TeXbook about \hbox{...} wants to emphasize that no stretching or shrinking of glue is done. If you do \setbox0=\hbox{a\hfill b}, then \box0 will have ‘a’ and ‘b’ next to each other, because the natural width of \hfill is 0pt. However, the contents of a box register can be unfrozen if you do \unhbox0 (or \unvbox for vertical boxes): a level of boxing is removed and the glue contained in the boxes regain their ability to stretch or shrink.

In a math formula, something between braces (not delimiting an argument) is treated as a subformula which is boxed similarly to \hbox{...} before, so glue inside it will not participate to stretching or shrinking. The subformula itself will be handled as an ordinary atom when boxing the outer formula.

The babel manual has frozen in a footnote about hyphenation. TeX is able to load hyphenation patterns only when it is making a format. When you run pdflatex file, you are actually running

tex &pdflatex file

where & means “load the file called pdflatex.fmt”, which contains a memory dump of TeX in some well defined state. The footnote mentions lccodes and is about a rather technical point. Hyphenation in TeX relies both on patterns and the \lccode array. The status of the array when hyphenation patterns are loaded during format creation is saved in the memory dump together with the digested patterns and is not modifiable.

There are also other frozen things in LaTeX: \frozen@everymath and \frozen@everydisplay, which are internal aliases for the primitive token registers \everymath and \everydisplay. LaTeX then reallocates \everymath and \everydisplay as standard token registers, in order to have a “safe” starting point: for instance \frozen@everymath does \check@mathfonts and it's very important this macro is executed at the beginning of every formula. If \everymath was used, a package code could modify the register and forget to add the important bit. Thus LaTeX has

\let\frozen@everymath\everymath
\newtoks\everymath
\frozen@everymath = {\check@mathfonts\the\everymath}

so doing something like \everymath{\displaystyle} (it's just an example, don't do it) will not clobber the important \check@mathfonts.

Finally, what's a frozen catcode? Nothing special. It's just an idiom to mean that when input is read in by TeX, catcodes are assigned to each character according to the current status of the \catcode array and cannot be modified (unless the token list is tokenized again via \scantokens).