Jeff, I disagree, load balancing does not imply redundancy, it's quite the opposite in fact. The more servers you have, the more likely you'll have a failure at a given instant. That's why redundancy IS mandatory when doing load balancing, but unfortunately there are a lot of solutions which only provide load balancing without performing any health check, resulting in a less reliable service.
DNS roundrobin is excellent to increase capacity, by distributing the load across multiple points (potentially geographically distributed). But it does not provide fail-over. You must first describe what type of failure you are trying to cover. A server failure must be covered locally using a standard IP address takeover mechanism (VRRP, CARP, ...). A switch failure is covered by resilient links on the server to two switches. A WAN link failure can be covered by a multi-link setup between you and your provider, using either a routing protocol or a layer2 solution (eg: multi-link PPP). A site failure should be covered by BGP : your IP addresses are replicated over multiple sites and you announce them to the net only where they are available.
From your question, it seems that you only need to provide a server fail-over solution, which is the easiest solution since it does not involve any hardware nor contract with any ISP. You just have to setup the appropriate software on your server for that, and it's by far the cheapest and most reliable solution.
You asked "what if an haproxy machine fails ?". It's the same. All people I know who use haproxy for load balancing and high availability have two machines and run either ucarp, keepalived or heartbeat on them to ensure that one of them is always available.
Hoping this helps!
Using "sticky (persistent) sessions" is generally not advised. If you do this, you lose a lot of the benefits of load balancing. The load will not be balanced and you will lose high availability, as certain clients will be unable to access your application in case of failure.
You want your session to be dynamic. With Java, it's typically stored in memory and clustered to all servers via multicast. More commonly, the session will be stored in a database.
If your Web application requires sticky sessions, your architecture may need improvements.
As far as load balancer solutions, there are many out there and the subject has been covered extensively here. I like LVS. Others like nginx. Foundry Networks, which was acquired by Brocade, makes some solid commercial products. They're the main commercial solution for hardware load balancers. Barracuda also has a Linux/OSS-based "appliance" that can be used for Load Balancing.
Best Answer
I can't speak to NLB specifically with regards to load balancing WCF services, but I've supported and built out many load balanced WCF web services in the past. Overall, I wouldn't recommend using NLB, outside of a Dev environment, as NLB does not scale well. However, if you don't have access to a hardware load balancer or the desire to get into Linux (HAProxy/Varnish/Nginx), it can work.
So:
The only caveat that I have to any of this is more to do with load balancing WCF than with NLB. If you plan on using SSL with your WCF service, and you transition to a load balancer that supports SSL-offloading, you may run into issues with the WSDL not being available through the VIP (virtual server IP address). There are workarounds, but since you're not there yet, I just wanted to make you aware of it, not freak you out.
EDIT: I was going to elaborate on how to address metadata in an SSL-offload scenario, but a recent MSDN blog post handles it much more elegantly:
http://blogs.msdn.com/b/dsnotes/archive/2014/10/03/ssl-offloading-in-load-balancer-scenario.aspx
The gist is that there are two options, modifying the customBinding to allow enableUnsecuredResponse or to modify the WSDL completely to make it available over HTTPS on the server. Option 2 is the more effective way to handle this, as it will allow for better compatibility with non .NET technologies.