How does dired determine which ls program to use when running over tramp? I couldn't find it anywhere in the document. If it is insert-directory-program, what would it do if the path doesn't exist on the remote host?
Tramp does not use insert-directory-program. It has its own mechanism to detect a proper ls program.
Dired is not involved at all. It calls insert-directory, and let the local implementation, or the Tramp implementation run.
insert-directory-programto a value which doesn't exist on the remote host?