Esta resposta é simplista, mas tenta dar uma ideia. Imagine que os programas são uma lista de solicitações para fazer algo.
Assim como num restaurante onde voce faz o pedido informando que quer bem passado, com ou sem cebolas, ..., isto é só o pedido (seu programa). Quem vai realmente preparar o prato (o kernel do sistema operacional) está na cozinha tenta preparar de acordo com o seu pedido (o programa).
Você só comerá o que quer se falar a mesma do cozinheiro.
O cozinheiro do linux fala ELF e o do windows fala PE. Então normalmente um não entende os pedidos feitos para o outro.
Mas tem alguns que são bilíngues e conseguem entender outros formatos. Um projeto muito legal é o wine que roda executáveis do windows no linux (por vezes com performance melhor que no próprio windows).
Então é só uma questão de entender o idioma para se comunicar com o sistema operacional.
Aqui tem um link para alguns tipos de formato de executável (em espanhol, mas acho que dá para ter uma idéia que tem um monte)