How does program execute? Where does the Operating Systems come into play?

For starters, a modern CPU has (at least) two modes, a mode in which it's running the core of the Operating System itself ("kernel mode") and a mode in which it's running programs ("user mode"). When in user mode, the CPU can't do a whole lot of things.

For instance, a mouse click is typically noticed in the kernel, not user mode. However, the OS dispatches the event to user mode and from there to the correct program. The other way around also requires cooperation: a program can't draw to the screen freely, but needs to go through the OS and kernel mode to draw on its part.

Similarly, the act of starting a program is typically a cooperation. The shell part of the OS is a user-mode program too. It gets your mouse click, and determines that it's a mouse click intended to start a process. The shell then tells the kernel-mode part of the OS to start a new process for that program.

When the kernel mode needs to start a new process, it first allocates memory for bookkeeping, and then proceeds to load the program. This involves retrieving the instructions from the binary, but also hooking up the program to the OS. This usually requires finding the entry point (classically int main(int argc, char** argv)) of the binary, and all points where the program wants to call the OS.

Different Operating Systems use different ways to hook up programs with the OS. As a result, the loading process differs, and the file formats for binaries can differ too. It's not absolute; the ELF format for binaries is used for a number of Operating Systems, and Microsoft uses its PE format on all its current Operating Systems. In both cases, the format does describe the precise format of the binary, so the OS can decide whether the program can be hooked up to the OS. For instance, if it's a Win32 binary, it will be in the PE format, therefore Linux won't load that, Windows 2000 will, as will Windows 7-64. A Win64 binary on the other hand is in PE format too, but Windows 2000 will reject it.

It will not run on other processors since 01010110011 means something on x86 and something else on ARM. x86-64 happens to be backwards compatible with x86 so it can run x86 programs.

The binary is in a specific format that your OS understands (windows = PE, mac/linux = ELF)

With any normal binary, your OS loads it into memory and populates a number of fields with certain values. These "certain values" are addresses to api functions that exist in shared libraries (dll, so) such as kernel32 or libc. The API addresses are needed because the binary itself does not know how to access hard drives, network cards, gamepads etc. The program uses these addresses to invoke certain functions that exist in your OS or in other libraries.

In essence, the binary is missing some vital parts that need to be filled by the OS to make everything work. If the OS fills in the wrong parts, the binary won't work since they can't communicate with each other. That's what would happen if you would replace user32.dll with another file, or if you try to run a linux executable on mac osx.

So how does libc know how to open a file?

libc uses syscalls, which is low-level access to the OS core functions. It's sort of like a function call except you do it by populating certain CPU registers and then triggering an interrupt (special CPU instruction)

So how does the OS then know how to open files?

That's one of the things an OS does. But how does it know how to talk to a hard drive? I don't know exactly how that stuff works but I imagine the OS does this by writing/reading certain memory locations which happen to be mapped to BIOS functions.

So how does the BIOS know how to talk to a hard drive?

I don't know that either, I've never done any programming at that level. I imagine the BIOS is hardwired to the hard drive connectors and is able to send the correct sequence of 1 and 0 to talk "SATA" with the hard drive. It can probably only say simple things such as "read this sector"

So how does the hard drive know how to read a sector?

I really don't know this at all so I'll let some hardware guy continue.

Two ways:

First and foremost the answer is "system calls". Whenever you call a function that needs to do any I/O, interact with devices, allocate memory, fork processes, etc., that function needs to do a "system call". While the syscall instruction itself is part of X86, the available system calls and parameters to them are OS-specific.

Even if your program doesn't make ANY system calls (which I'm not sure is possible, and certainly wouldn't be very useful) the formats that wrap around the machine code are different for different OSes. So the file formats of exe (PE) and a linux executable (ELF usually) are different, which is why an exe file won't execute on Linux.

EDIT: these are low-level details. The higher-level answer is to say that anything that needs to access files, the console/GUI, allocate memory, etc. is OS-specific.