The nature of NAT is such that someone on the outside can find the NAT box (commonly a home broadband router in our context), but they can't find the computers attached behind it.
Imagine finding an apartment building, and finding a door bell panel with thousands of buttons. If you've been invited by a tenant, they've told you which of the many buttons is theirs. And they can tell you what pattern to tap-out so they'll answer. If you're just walking down the street looking for people to bug, not only will it be unlikely that you'll find the right button, it's even less likely that you'll know the right pattern to tap-out to get an answer if you do find a button that attaches to something. For all practical purposes, you're locked-out.
What NAT can't protect you from is attacks from within. If you allow a trojan in (perhaps a drive-by download from a website you visited), it can invite problems in when it phones home. In this case, the attack will know which button to press, and what pattern to tap-out because it's being invited in behind your back.
The most effective way of fighting these problems is a software firewall that monitors programs attempting to make outbound connections. The problem is that these programs usually will ask a user if they want to allow a connection, and many of the people who are most prone to inadvertently allow these trojans to enter in the first place are also prone to rubber-stamp any outbound connection request with a "yes". (Or at least they are once they discover that rubber-stamping with a "no" can disconnect them from the Internet all together.)
But for someone who's alert, this level of protection, along with regular scans for viruses, trojans, spyware and adware, along with the intrinsic protection of NAT, will be sufficient.
However, if you happen to have information that needs to be protected for National security issues, or have some other data that makes you a real target of people other than script-kiddies, relying on a software firewall running on the same machine that it's trying to protect is like hoping an interior door in your house will protect the house. If they're already into the machine, half their objective is met, and getting past a piece of software is as easy as knowing how to remotely disable it.
There are external firewall boxes offering various levels of security well beyond what NAT and a software firewall. But frankly, most home users don't need to invest in these anymore than they need to invest in an electric fence, a moat, or an armed guard to protect their homes. They're just overkill for most people.
So to more directly answer your question, NAT, along with a software firewall that monitors outbound connections, and regular scans of your computer by anti-virus (etc.) programs is sufficient for most users, and a true hardware firewall is not required. And yes, NAT is a very important component of this strategy.