Q:

How Linux decides what `malloc` to use? 

I know how to replace malloc with LD_PRELOAD; library that preloaded gets priority, so if we preload jemalloc, executable gets its malloc version. 
However, when we build application with -ljemalloc, we also link it against glibc.  How Linux knows that it has to use jemalloc malloc and not glibc one?  What if I will link both jemalloc and tcmalloc, we'll have 3 malloc now, what and why Linux (or may be the linker, I am not sure) will select? 

A:

You can check the order of libraries being loaded by running:
strace -ff -s 999 YOUR_BINARY 2>&1 | grep -e 'library1' -e 'library2'
The order should match the output from ldd YOUR_BINARY. 
And yes, as already noted, the first library will get priority.