Whilst NAT discards all unsolicited traffic received from the Internet, it does not restrict conversations initiated by the computers behind it. A software firewall (and it's user) would theoretically prevent malicious programs from initiating these 'outbound' conversations. It is worth noting that the most common type of malicious, network-aware program, the Remote Access Trojan (RAT), almost always depends upon an inbound connection from the attacker and is therefore defeated by NAT alone.
Although the threat reduction provided a software firewall employed in this scenario may be relatively small they do provide another layer of defense against certain types of malicious program and may be useful in alerting you to the presence of such.
As detailed previously, NAT discards all unsolicited traffic received from the Internet. Therefore, a software firewall watching inbound traffic would only ever see return traffic - traffic that is part of a conversation initiated by the host computer. Besides the occasional false positive (see here for an example), the software firewall will never produce any 'alerts' on inbound traffic.
So, why do people run them? Well, the advantage that a software firewall holds over hardware devices is that it can associate conversations with the program involved. A standalone NAT or firewall device has no way of determining which program is responsible for the packets it filters - it can only filter on the fields in packet headers such as ports and addresses. If an administrator were to filter all outbound connections except those destined for port 80 (http) they could not assume that the only conversations passing through the device were indeed http. Indeed, some legitimate programs (IM and P2P clients, etc) allow users to set a "firewall mode" whereby they use destination port 80 for all conversations, bypassing "pesky admins and their firewalling" (and often their security policies).
A software firewall can tell you which program is initiating conversations and most ask the user to permit or deny communications for each application, remembering and automatically applying the decision in the future. This can provide protection in the case of the inadvertant running of a malicious program which is programmed to send out your private data or connect out to somebody, offering some degree of control over your 'infected' computer. It is important to note that this protection is dependent on the user, who must decide whether or not to allow the new program to communicate. This is often the weak link, especially considering that the same user just 'chose' to run the malicious program. Making effective use of a software firewall requires some knowledge - they generate a low signal-to-noise ratio and identification of 'the signal' requires a basic familiarity with TCP/IP and the software installed on your system. As with many tools, a software firewall is only as good as it's user.
The most common type of malicious, network-aware program is the Remote Access Trojan (RAT), which typically has two components - a server which is run on the victim's computer (usually by the victim!), and a client that's used to connect to it. This type of program will be foiled by NAT alone since the client -> server connection is impossible. The only type of network-aware program NAT will not protect against is one that does not rely on an inbound connection. These are relatively rare.
A malicious program that does not depend upon an inbound connection (i.e. that connects out) would have to have the connection parameters hard-coded. This is not ideal for the attacker since the remote address (their own if they're particularly dumb) can be easily discovered. If the trojan is designed to send out private data, the location of the data would need to be hard-coded (or searched for). Therefore this type of trojan does not lend itself well to mass use - the address(es) to which it connects would eventually be found and presumably brought offline / cleaned up. Perhaps it is fair to say that this type of program would typically be used in directed, personal attacks.
Of course, there are exceptions, the most obvious being a program which connects to an Internet Relay Chat (IRC) server. This offers a degree of anonymity to the attacker but a limited interface for interacting with the programs running on 'infected' computers. An example of this type of program is some types of DDoS zombie agent. Whilst perhaps not malicious, so-called 'adware' and 'spyware' programs make outbound connections to deliver you adverts or transmit browsing statistics.
Unsurprisingly, malicious programs do not just magically appear on your hard drive and start running. In almost all cases, the victim is personally responsible for the procurement and execution of malicious code. Usually this self-harm is committed via the double-clicking of an email attachment or the download and execution of, for example, a program purporting to be a "fun game" or "cool screen saver". It's important to note that a software firewall will not stop you from acquiring or running such programs. It will only intervene if and when the program initiates a network conversation. This might be after the program has terminated the software firewall or deleted important files. It might never happen at all (perhaps the program simply formats your hard disk).
Clearly, a software firewall employed as a security measure in this scenario should only be considered as a last resort backup against the subset of malicious code that is network-aware. If your existing measures against malicious code in general (common sense included) are up to scratch, a software firewall may well be a waste of both your and your computer's resources. If they are not, you really need to make them so!
As with all security measures, the decision to run a software firewall should be based upon an evaluation of the cost / benefit ratio. A software firewall uses memory and CPU time on the host computer, requires proper configuration, frequent user interaction and often produces false positives in (usually overly dramatic) alerts and logs. However, it may someday aid an aware user in the detection of a malicious program that has evaded their other defenses and attempted to initiate a network conversation. In addition, they can be useful for control over the network activities of legitimate programs and adware / spyware annoyances. The exact value of this ratio in any particular situation is something the reader must decide for themselves.
Feedback received on this FAQ entry: