How are variable names stored in memory in C?

Question 1

Variable names don't exist anymore after the compiler runs (barring special cases like exported globals in shared libraries or debug symbols). The entire act of compilation is intended to take those symbolic names and algorithms represented by your source code and turn them into native machine instructions. So yes, if you have a global variable_name, and compiler and linker decide to put it at 0xaaaaaaaa, then wherever it is used in the code, it will just be accessed via that address.

So to answer your literal questions:

How does the compiler recognize that the string "variable_name" is associated with that particular memory address?

The toolchain (compiler & linker) work together to assign a memory location for the variable. It's the compiler's job to keep track of all the references, and linker puts in the right addresses later.

Is the string "variable_name" stored somewhere in memory?

Only while the compiler is running.

Does the compiler just substitute variable_name for 0xaaaaaaaa whenever it sees it, and if so, wouldn't it have to use memory in order to make that substitution?

Yes, that's pretty much what happens, except it's a two-stage job with the linker. And yes, it uses memory, but it's the compiler's memory, not anything at runtime for your program.

An example might help you understand. Let's try out this program:

int x = 12;

int main(void)
{
    return x;
}

Pretty straightforward, right? OK. Let's take this program, and compile it and look at the disassembly:

$ cc -Wall -Werror -Wextra -O3    example.c   -o example
$ otool -tV example
example:
(__TEXT,__text) section
_main:
0000000100000f60    pushq   %rbp
0000000100000f61    movq    %rsp,%rbp
0000000100000f64    movl    0x00000096(%rip),%eax
0000000100000f6a    popq    %rbp
0000000100000f6b    ret

See that movl line? It's grabbing the global variable (in an instruction-pointer relative way, in this case). No more mention of x.

Now let's make it a bit more complicated and add a local variable:

int x = 12;

int main(void)
{  
    volatile int y = 4;
    return x + y;
}

The disassembly for this program is:

(__TEXT,__text) section
_main:
0000000100000f60    pushq   %rbp
0000000100000f61    movq    %rsp,%rbp
0000000100000f64    movl    $0x00000004,0xfc(%rbp)
0000000100000f6b    movl    0x0000008f(%rip),%eax
0000000100000f71    addl    0xfc(%rbp),%eax
0000000100000f74    popq    %rbp
0000000100000f75    ret

Now there are two movl instructions and an addl instruction. You can see that the first movl is initializing y, which it's decided will be on the stack (base pointer - 4). Then the next movl gets the global x into a register eax, and the addl adds y to that value. But as you can see, the literal x and y strings don't exist anymore. They were conveniences for you, the programmer, but the computer certainly doesn't care about them at execution time.

Question 2

A C compiler first creates a symbol table, which stores the relationship between the variable name and where it's located in memory. When compiling, it uses this table to replace all instances of the variable with a specific memory location, as others have stated. You can find a lot more on it on the Wikipedia page.

Question 3

All variables are substituted by the compiler. First they are substituted with references and later the linker places addresses instead of references.

In other words. The variable names are not available anymore as soon as the compiler has run through

Question 4

This is what's called an implementation detail. While what you describe is the case in all compilers I've ever used, it's not required to be the case. A C compiler could put every variable in a hashtable and look them up at runtime (or something like that) and in fact early JavaScript interpreters did exactly that (now, they do Just-In-TIme compilation that results in something much more raw.)

Specifically for common compilers like VC++, GCC, and LLVM: the compiler will generally assign a variable to a location in memory. Variables of global or static scope get a fixed address that doesn't change while the program is running, while variables within a function get a stack address-that is, an address relative to the current stack pointer, which changes every time a function is called. (This is an oversimplification.) Stack addresses become invalid as soon as the function returns, but have the benefit of having effectively zero overhead to use.

Once a variable has an address assigned to it, there is no further need for the name of the variable, so it is discarded. Depending on the kind of name, the name may be discarded at preprocess time (for macro names), compile time (for static and local variables/functions), and link time (for global variables/functions.) If a symbol is exported (made visible to other programs so they can access it), the name will usually remain somewhere in a "symbol table" which does take up a trivial amount of memory and disk space.

Question 5

Does the compiler just substitute variable_name for 0xaaaaaaaa whenever it sees it

Yes.

and if so, wouldn't it have to use memory in order to make that substitution?

Yes. But it's the compiler, after it compiled your code, why do you care about memory?