I need to setup Network Address Translation (NAT) for a LAN, which uses Samba to support Windows clients. There is only one DSL IP address, but about 4 computers on the LAN. They all need to have Internet access, does Linux support NAT with Samba?

Linux can support any linux based program... so in a short answer: 'yes' it can support samba and NAT/DHCPd/etc. at the same time.

Basically, all that is required is for the software to be installed, and configured, there should be no conflict between the application/services you mentioned above.

http://linas.org/linux/load.html
This site provides a good deal of information regarding NAT on Linux, including some applications which can make it possible. Of course this forum is also a great source of information, but you will need to specify more clearly what you are needing help with before I can provide any valuable assistance.