does the compiler has to attach the GC to the final executable? Or is it like a dependency that has to be already available on the target machine?

This depends on the language implementation and the target platform.

It’s possible that the GC gets linked into the executable, it’s also possible that the GC is part of the runtime library, and it’s possible that the GC is a part of the target platform.

If it’s attaching the GC, then should I think of it as a Wrapper around my application that once in a while stops the execution, does some clean-ups, recovers the state of the application and let it continue the execution?

Wrapping is only needed when the application doesn’t know that it is being garbage-collected. The Boehm-Demers-Weiser collector is a GC for C and C++ programs that don’t even know that they are being GCed. You can just replace all calls to malloc/realloc with calls to GC_malloc/GC_realloc and remove all calls to free (for example by redefining them using a macro) and everything will still work.

However, programs written in a language with automatic storage management already know they are being collected, there is no need to wrap them.

Also, again, it depends on the GC implementation whether or not it has to “stop-the-world”. Some GCs need to stop the application for the whole collection. Some only need to stop it for one phase of the collection. Some are incremental, i.e. they don’t need to do all work at once, they can do a little bit of work, then let the application run a bit, do a little bit of work, let the application run …

Some collectors are concurrent, they can collect while the application is running without any need to stop it at all.

Also I think some languages like Java have their own GC included in their VM. In that case I’m only talking about languages that directly compile to the machine code and don’t need any VM to execute.

There is no such thing as a “language that compiles directly to machine code”. That depends on the language implementation. Languages don’t compile, compilers do. Every language can be interpreted, every language can be compiled to machine code or any other language.

The Java Language Specification says that memory is managed automatically. How the implementation does that, is completely up to the implementor. Oracle javac compiles to JVM bytecode, which also manages memory automatically, so the javac doesn’t need to worry about GC. GCJ, for example, compiles Java to native code and links it with a GC based on the Boehm-Demers-Weiser GC.

In D the standard runtime that gets linked in during compilation includes the implementation of the GC.

How the GC does the inspection of the program state depends on implementation. There is a stop-the-world type that uses a system call to suspend all program threads and lets the GC thread inspect the program without worrying about other threads invalidating the inspection (the mark fase, the sweep can work concurrently because you just proved no other thread will access the memory you are freeing).

However concurrent GCs exist that can do the inspection while the program is running; though that usually requires some support from the program threads.