Others have answered the question but the reason this works in CL is rather simple: Function calls (by default) have a single level of indirection. When CL calls a function it looks up the address of the function in a table (the symbol table), then jumps to the given address. If you redefine the function associated with the symbol, the next call gets the new definition. Yes, you need a separate thread (native or green) for the REPL but it has less to do with the REPL being a separate thread and more to do with the symbol table being a global data structure.
This is why there is no "linking" step in Common Lisp compilation: CL keeps the symbol table around at runtime; C just throws it away.
Note, however, that a CL compiler is allowed to assume that calls to functions defined in the same file are to that definition (so it can short circuit the function lookup.) This is from the CLHS section 3.2.2.3. http://clhs.lisp.se/Body/03_bbc.htm
"All conforming programs must obey the following constraints, which are designed to minimize the observable differences between compiled and interpreted programs:"
[...]
"A call within a file to a named function that is defined in the same file refers to that function, unless that function has been declared notinline. The consequences are unspecified if functions are redefined individually at run time or multiply defined in the same file."
I suspect this has to do with deferring warnings from forward definitions, but I might be wrong. It's still common behavior for REPL redefinition to have an immediate effect on the next function call unless that function was declared inline. (Regardless of what file the function was defined in.)
This is why there is no "linking" step in Common Lisp compilation: CL keeps the symbol table around at runtime; C just throws it away.