What is NAT?
NAT is 'Network Address Translation', and is the solution to the problem: "I have one IP address, and I want to share it between 'n' hosts".
With a NAT'd network, the gateway (which hosts the network's one publicly routable IP address) divides the world into "public" and "private" address spaces. When a host on the private network tries to connect to the outside world, the NAT gateway silently rewrites the packet so that it appears to come from some port on the gateway, hiding the internal address. When a reply comes back from the public Internet, the gateway reverses its mapping, sending the packet to its true, hidden destination.
Connectionless protocols such as UDP are rewritten on a "best guess" basis (if they are handled at all).
Is NAT a Firewall?
Technically, yes. A NAT box is a special-case of a stateful firewall. Hosts inside the firewall can send packets out and establish connections. Once a connection is initiated from inside the network, data can flow freely until that connection is closed. Hosts outside the firewall, however, are unable to initiate connections to hosts inside unless a tunnel is specifically provided by the NAT box's administrator.
As such, it's important to note that you get almost no security from NAT that you can't get with a halfway-decent stateful firewall. Setting up such a firewall to give you identical protection without the address translation would take all of sixty seconds. The only benefit you get is that because NAT'd internal addresses come from the non-routable IP address space, the Internet might protect you from some obscure, creative exploitation of a bug in your firewall. But it probably won't.
On the other hand, NAT is very inflexible. It is possible to allow services within the network to be accessed from the outside by creating a tunnel so that when somebody connects to, say, port 80 of the NAT gateway, they are silently redirected to a webserver on an internal address. However, because this completely uses up port 80 on the gateway, you can't just add a second webserver later. Similarly, if you have 20 people in the private network all of whom want to use a network client that listens connections on port 3324, all but one of them will be out of luck.
What's Wrong with NAT?
The downsides of NAT can be quite subtle. Essentially, what it creates is a two-tier1 Internet: one group of people who can both establish and receive connections, and another group who can only establish them. (Thinking of it as a read-write or read-only Internet connection is a useful metaphor, even if it's completely inaccurate)
Don't get me wrong. Blocking the ability for the outside world to establish connections to your private network is particularly useful, and something most firewall administrators would approve of in the general case. It's just that NAT is really bad at handling exceptions. Trying to manage the protocols you want to work through the NAT box becomes impossible the moment you want them to apply to more than one host.
A few years ago, when I had a NAT'd network, I would turn on Napster just so I could be amused at all the people trying (and failing) to access my ripped CD collection. I could connect to the directory, but nobody could connect back to me to get the songs. Similarly today, back behind NAT again, I have endless problems with IM clients and file-transfers.
Creators of new Internet protocols end up with two choices: either exclude the (significant, and constantly growing) population of NAT users, or over-complicate your protocol by having it try connecting in both directions in the hope that one will allow the link to take place. The prevelance of NAT gives us the choice between sacrificing simplicity or sacrificing users.
Some protocols, such as KaAaA's new voice-chat application, Skype, even go as far as having the connection piggyback on a non-NAT'd intermediary. While this is clever, it's still a work-around to the underlying problem, not a solution.
NAT is also used as an excuse for hanging on to IPv4. “We're not running out of IP addresses”, is the cry "We have enough to last us until 2020!" Certainly we do, at our current level of usage. But if there's no scarcity, why is it so hard for Joe Average to get a block of them for his home network off the cable provider? The idea of there being a scarcity of numbers is, frankly, ridiculous2. We justify the continuation of the address-space status quo through the wide availablility of NAT as a 'cheap alternative'.
As you may have gathered, I'm not a big fan of Network Address Translation. Its security benefits are minimal compared to a similarly configured firewall, and its disadvantages are legion. It's a tool that's blocking the free flow of data, segmenting the Internet and bloating protocols, while at the same time being misused as an excuse not to improve the infrastructure surrounding it. This is just a bad thing.
1 Actually, the Internet has been developing tiers all over the place. There's also the class distinction of static vs dynamic IP addresses: another thing that should3 go away if we had a larger address space.
2 Dear Internet-at-large. It's spelled 'ridiculous', not 'rediculous'. Also, while I'm at it, the opposite of 'win' is 'lose'. It's not 'loose'.
3 I say "should", because service providers have a significant interest in maintaining the dynamic-IP system, many even cycling IP addresses on otherwise always-on connections like cable modems, so they can create an artificial price differential between home and business accounts.