In brief:

How does Perl know not to compile it again?

Any change to the C code (including changes affecting only whitespace) will be detected as a change to the MD5 fingerprint, and the code will only then be recompiled.
Changes to Inline configuration options will not alone trigger a rebuild - unless it's the FORCE_BUILD option that is being changed to a TRUE value.

And where does the compiler save the binaries when done?

Generally the building is done in ./_Inline/build and the binaries saved in ./_Inline/lib, but the name of the parent directory is configurable.

How are these binaries named?

A combination of the filename of the script, and the leading hex digits of the MD5 fingerprint of the code section.

Cheers,
Rob