What makes a Linux distribution GNU? Is it the tools, with which the kernel was compiled? Is it the tools, with which the distribution is shipped?
Yes and yes. The kernel is one monolithic stand-alone executable. Everything else resides in "userland". Generally, userland applications make use of at least one system library, the standard C library.1 In addition to various utility functions, this is what provides access to system calls -- requests for the system, i.e., the kernel, to do something -- which is necessary for even very basic tasks, such as working with files. The C library implementation used with linux is glibc -- the GNU C library.
The linux kernel itself is written in C, and also requires a C library to work -- except in this case the necessary parts are compiled in, and not external. The compiler normally used for this is GCC -- the "GNU Compiler Collection" -- and the C library is glibc.
Since virtually all of the userland is compiled against glibc, it is one of the most essential things on the system after the kernel. Another essential component is the linker, which connects an executable to an external library. That's a GNU product too.
To illustrate this, you can use
ldd on various executables, including libraries (which are executable, but not on their own). As it says in the man page, "ldd prints the shared libraries required by each program or shared library specified on the command line." E.g.:
> ldd /bin/bash
linux-vdso.so.1 => (0x00007fff7348e000)
libtinfo.so.5 => /lib64/libtinfo.so.5 (0x00007fdbdae7f000)
libdl.so.2 => /lib64/libdl.so.2 (0x00007fdbdac7b000)
libc.so.6 => /lib64/libc.so.6 (0x00007fdbda8c3000)
Notice "libc.so.6" -- that's glibc (don't confuse it with glib, another GNU product fundamental to linux, but not as fundamental as glibc). If you look at all the other things mentioned (except the first one, explained below), you'll notice they all link to libc themselves. Let's look at libc.so.6 itself:
> ldd /lib64/libc.so.6
linux-vdso.so.1 => (0x00007fffb21ff000)
"ld-linux-x86-64.so.2" is the linker mentioned above (generally,
ld, and it has a man page). You can't run ldd on it but
file says it is dynamically linked, I presume to libc (this may sound circular, but it isn't) and linux-vdso. This last one is sort of interesting because you'll notice just an address after the
=>. That's because it is actually part of the kernel.
The C library, AFAIK, is the only shared object on the system that doesn't link to the C library -- it's at the center of the whole mess. Even the base library of other compiled languages uses libc, e.g.:
> ldd libstdc++.so.6.0.17
linux-gate.so.1 => (0xf77b8000)
libm.so.6 => /lib/libm.so.6 (0xf7684000)
libc.so.6 => /lib/libc.so.6 (0xf74d2000)
libgcc_s.so.1 => /lib/libgcc_s.so.1 (0xf74b5000)
Note that libraries and the linker have various pseudonyms implemented with symlinks (e.g., /lib64/ld-linux-x86-64.so.2 is actually /lib64/ld-2.15.so).
Also note that
gcc, the "native" compiler (since it compiles the kernel, and the C library) does not have to be present on the system, but libc and ld do or else nothing can work.
That's not the only set of things in that GNU provides. They also are responsible for the
bash shell and other core tools and utilities that make the system *nix like and (mostly) POSIX compatible. And GNOME, one of the first linux DE's and one of the most widely used. And the aforementioned glib, which provides a lot of high level functions to support things like a GNOME and other DE's. GNOME is built on GTK, which was originally developed for the GIMP. GTK is also fundamental to various other DE's; GTK and the GIMP are also GNU products. They've done a lot of stuff.
1 There is such a thing as a userland application that doesn't link to any library; these are called static executables and it essentially means they have had parts of that library compiled into them (just like the kernel does).