Um proxy HTTP funciona na camada de aplicativo. NAT trabalha na camada IP. Estas são duas coisas completamente diferentes que não se conhecem e não operam no mesmo nível. Portanto, sua pergunta não faz muito sentido.
Quando um proxy HTTP recebe uma solicitação para uma página da Web (e supondo que a página da Web ainda não esteja no cache do proxy), ela abrirá sua própria conexão TCP com o servidor HTTP de destino, emitirá sua própria solicitação HTTP, analisará a resposta HTTP e, em seguida, encaminha a resposta para o cliente, que tem sua própria conexão TCP com o proxy. Um proxy HTTP apenas entende o protocolo HTTP e não faz proxy de nenhum outro protocolo (note que, para simplificar, estou deixando de lado coisas mais confusas, como CONNECT ou proxies de uso múltiplo).
NAT é completamente diferente. Ao encaminhar uma conexão HTTP através de um NAT, há apenas uma conexão TCP direta do cliente para o servidor, o NAT está envolvido apenas em monitorar qual terminal interno (endereço e porta) está falando com qual terminal externo (endereço e porta). O NAT não abre conexões TCP, não sabe o que é HTTP, não analisa solicitações ou respostas, e certamente não armazena nada em cache. O NAT pode encaminhar qualquer protocolo (HTTP, ICMP, DNS ...), desde que seja baseado em IP, já que não precisa saber nada sobre o protocolo para operar.
Observe que estou descrevendo apenas configurações simples aqui. Existem configurações mais complicadas que podem ser confusas à primeira vista. Uma dessas configurações é um proxy transparente (também chamado proxy de interceptação), que fica no meio do caminho da rede e intercepta ativamente as conexões HTTP que os clientes tentam fazer para o exterior. Quando tal conexão é tentada, o proxy transparente reescreve o endereço de destino de tal forma que a conexão é redirecionada para o proxy. Depois disso, tudo se comporta como eu descrevi acima. Essa configuração é usada para forçar os clientes a passar pelo proxy sem precisar alterar sua configuração. Nesse cenário, os clientes podem até não estar cientes de que o tráfego HTTP está sendo intermediado por proxy, em vez de simplesmente NAT. Para obter informações mais práticas sobre proxies de interceptação, a documentação Squid tem um muita informação sobre isso.