Is it possible?

I have a linux router doing NAT for one external static IP address. I want to be able to access the machines behind it by hostname. I already have a decent setup where I can access any of the machines. I want to keep the inside machines listening on the same ports, i.e. 4834.

Is it possible for iptables to diffentiate between the hostnames I put in? Is this more of a DNS issue?

Hi,
that's definitely a DNS thing... if your DNS points to the correct IP address(es), the packets will come with the correct destination IP and nat/forwarding rules will send them to the right host.
Note that you can register a domain for free, and organisms like dyndns.org enable your domain name to point to the correct IP when you get a dynamic one (basically, you install a script that will update your IP address in dydns.org DNS servers).
Also, as far as web servers are concerned, you can set up virtual hosts with apache to redirect to the correct server according to the url.
Hope this helps.