How exactly does NAT protect a network? How does it relate to a firewall?
NAT acts as a firewall with a "default deny" policy for unsolicited incoming packets, but no other rules.
Because the machines behind a NAT box are not directly addressable (usually because they have private IP addresses), machines out on the general Internet cannot send IP packets to them directly. Instead, any packets will be sent to the address of the NAT box, and the NAT box looks at its records to see which outgoing packet an incoming packet is in reply to, to decide which internal address the packet should be forwarded to. If the packet is not in reply to an outgoing packet, there's no matching record, and the NAT box discards the packet.
NATing blocks incoming packets based on whether they are part of an established connection, not on their IP address, or protocol.
If there's an established connection, the packet is forwarded to the actual address. If not, it gets dropped.
For connectionless protocols, where there isn't a concept of an established connection (e.g. UDP), packets are allowed if they appear to be part of an ongoing conversation. This is necessarily a bit of a kludge.
NATing isn't only for private addresses, though private addresses wouldn't be much use without NATing.
NAT is allow-all outwards, allow-only-established sessions inwards.
For a user's PC, this can be roughly what you want, but for a server, it usually isn't.
For a server, you normally need to inbound connections on some known port/protocol combinations. (e.g. https/http to ports 443 and 80 for a webserver, smtp to port 25 for mail, etc). Not all firewalls can distinguish down to the protocol level, but some can.
And depending on what is inside the firewall, you probably don't really want to allow all outbound connections, only connections with a legitimate business purpose. For example, if you don't do business with Nigeria, do you want your servers connecting to Nigeria?
The days are gone when we can say outside=untrusted, inside=trusted. These days, it's more like outside=actively_hostile, inside=dubious. If (when) something gets inside the network, we want to make it a little bit hard for it to connect back to its controller, and we want to give ourselves a chance of detecting that there's something inside, knocking on the firewall.
NATing alone doesn't give us any of that.
It's useful. Sometimes it might be enough, maybe. It's certainly better than nothing. But it's not a full firewall.