A lot depends on how you use your system, but there are lots of discussions here on the subject. See the various firewall threads,
http://forum.avast.com/index.php?topic=49944.msg423404#msg423404 in particular for comments on NAT and firewalls.
Double NAT can be an issue with some games because of the need to "punch holes" in the NAT/firewall to allow inbound connections through two layers of protection. I prefer to set the modem up as a bridge and use the router capabilities for NAT and limited firewalling (I currently use a Netopia 3346 DSL router in bridge mode with a Linksys wrt54g wireless router with Tomato firmware).
So with your current setup you can restrict inbound traffic via NAT, allow outbound connections with perhaps a few restrictions, but generally treat your computer as a "black box". A software firewall gets you is the ability to restrict inbound and outbound connections by specific application, and provides you with insight into what is happening via the GUI. Many firewalls today add a HIPS (Host Intrusion Prevention System) that augments the firewall monitoring of the application connections with behavior monitoring of the application functions. So you have a way to see that something in your system is trying to phone home and is out gathering data to send out via the connection. With most hardware firewalls, the assumption is that outbound connections are OK. A mailbot shouldn't trigger alarms, for example, unless it was caught by the AV.
So I use both NAT and a software firewall/HIPS. A good modem/router like the Netopia also can make logs of the security stuff that happens at that interface, but this is usually for post mortem examination. Once the software firewall/HIPS is configured, the amount of real time popups you see depends mostly on how much "exploring" you intend to do and doesn't need to be intrusive. And AV/AM will always run a little behind the latest threats, so if you are an unlucky early victim the software firewall/hips may catch some new things with your interaction to the alerts.