É um vasto tópico para discutir. Mas considerando o caso do Ubuntu, as senhas são armazenadas no local
/etc/shadow
Você pode visualizar o conteúdo abrindo-o com
sudo nano /etc/shadow
Na primeira linha, você pode ver
root:$xrzOs5vu$gfLwd1NVOBRqCvmgpBOa9V4PzNOzlgC2jGU.GT8k9zPiW2zihymU/nmgdjsP8SzR3Qk7UoQUkTrsi9tCIFy6f.:16303:0:99999:7:::
A primeira parte é o nome de usuário (Aqui é a raiz. Você pode ver outros usuários abaixo). Em seguida, vem o formulário com hash da sua senha de root. Normalmente, uma vez que atribuímos uma senha ao ubuntu, ela gera um valor salt aleatório e adiciona esse valor salt ao arquivo de senha e, em seguida, o usa usando qualquer um dos algoritmos como sha512, md5, etc. Como o sal é desconhecido, é muito difícil para um cracker quebrar as senhas. Mas você ainda pode alterar sua senha de root simplesmente digitando o seguinte no terminal
sudo passwd