Boas perguntas, vamos lá!
Quando a função malloc é chamada, é passado um tamanho (em bytes), e ela devolve um bloco de memória contíguo daquele tamanho ou NULL caso não seja possível alocar um bloco destes. Isto vai ser importante logo mais.
Toda vez que um processo faz uma chamada para malloc (entre outras), embaixo dos panos é feita uma coisa chamada "System Call", isto é, uma chamada a código do Kernel do SO. (Se isso não ficar claro, tudo bem, estou dando spoilers de MAC-0422 aqui).
O importante é saber que quem decide se é possível ou não e sendo possível, qual pedaço da memória será "dado" ao processo é única e exclusivamente o S.O., que dá uma permissão para o processo usar aquela região.
Assim sendo, cada processo sabe quais blocos de memória são "seus". Essencialmente uma SegFault é uma tentiva de acesso a um bloco de memória no qual o processo não tem permissão para mexer.
Quanto à função free, ela recebe um endereço de um bloco contíguo de memória e novamente faz uma "System Call", informando ao S.O. que aquele espaço está disponível para ele novamente. O S.O. por sua vez, sabe qual era o tamanho do bloco dado, então todo o bloco que começava no endereço passado à função free está livre.
Acabei me empolgando um pouco na resposta, mas espero ter ajudado a entender um pouco melhor o que acontece.
Se ficou alguma dúvida (ou criou alguma nova), só postar aqui!