システムコールsys_execve()で、あるプログラムの
実行が始まるわけですが、ld-linux.soというのは
カーネルのどの部分でロードされるのでしょうか。

straceで観察するとlibc.soをロードするシステムコールは
発行されていますが、ld-linux.soに対してはありません。
これというのはカーネルがロードしていると考えていいわけですよね。
その後、ld-linux.soがlibc.soをロードする。