How, exactly, does the double-stringize trick work?

At least some C preprocessors let you stringize the value of a macro, rather than its name, by passing it through one function-like macro to another that stringizes it:

#define STR1(x) #x
#define STR2(x) STR1(x)
#define THE_ANSWER 42
#define THE_ANSWER_STR STR2(THE_ANSWER) /* "42" */

Example use cases here.

This does work, at least in GCC and Clang (both with -std=c99), but I'm not sure how it works in C-standard terms.

Is this behavior guaranteed by C99?
If so, how does C99 guarantee it?
If not, at what point does the behavior go from C-defined to GCC-defined?

Yes, it's guaranteed.

It works because arguments to macros are themselves macro-expanded, except where the macro argument name appears in the macro body with the stringifier # or the token-paster ##.

6.10.3.1/1:

> ... After the arguments for the > invocation of a function-like macro > have been identified, argument > substitution takes place. A parameter > in the replacement list, unless > preceded by a # or ## preprocessing > token or followed by a ## > preprocessing token (see below), is > replaced by the corresponding argument > after all macros contained therein > have been expanded...

So, if you do STR1(THE_ANSWER) then you get "THE_ANSWER", because the argument of STR1 is not macro-expanded. However, the argument of STR2 is macro-expanded when it's substituted into the definition of STR2, which therefore gives STR1 an argument of 42, with the result of "42".

As Steve notes, this is guarenteed, and it has been guarenteed since the C89 standard -- that was the standard the codified the # and ## operators in macros and mandates recursively expanding macros in args before substituting them into the body if and only if the body does not apply a # or ## to the argument. C99 is unchanged from C89 in this respect.