It depends what devices the communication passes through.
Lets consider a network. A real network will have more hops but this shows all the important elements. All connections in the network we are considering are ethernet.
Client<-->Ethernet switch<-->NAT<-->IP router<-->server
Now lets say the client goes to set up a TCP connection to the server.
The client builds a packet. It's source MAC is set to it's own MAC address. It's destination MAC is set to the MAC of the relavent port on the NAT box. It's source IP is set to the clients private IP. It's destination IP is set to the IP of the server. It's source port is set to the port the client is bound to (which is usually selected randomly). It's destination port is set to the port for the desired service on the server.
The Ethernet switch simply passes the frame on. It doesn't change any addresses.
The NAT strips off the Ethernet headers. It then modifies the IP headers changes the source IP address to it's public IP. It may also change the source port to disambiguate connections from different clients. The destination IP and port remain unchanged. A mapping table entry is created so that reverse translation can be performed. New Ethernet headers are then built with the source MAC being the MAC of the relavent port on the NAT box and the destination MAC being the MAC of the relavent port on the IP router.
The IP router strips off the Ethernet headers and again builds new ones so the packet can be sent to the server.
The packet arrives at the server, a reply is generated and a similar process proceeds to get the packet back to the client.