How are variable names stored in memory in C?

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 exampleexample:(__TEXT,__text) section_main:0000000100000f60    pushq   %rbp0000000100000f61    movq    %rsp,%rbp0000000100000f64    movl    0x00000096(%rip),%eax0000000100000f6a    popq    %rbp0000000100000f6b    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   %rbp0000000100000f61    movq    %rsp,%rbp0000000100000f64    movl    $0x00000004,0xfc(%rbp)0000000100000f6b    movl    0x0000008f(%rip),%eax0000000100000f71    addl    0xfc(%rbp),%eax0000000100000f74    popq    %rbp0000000100000f75    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.

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.

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