What's the best practice for getting EC2 instances to join HAProxy automatically?

Question

We're working on scaling out our EC2 architecture to a point where we'd like to manage our own load balancing. We currently have a series of machines configured on HAProxy to do basic load balancing, but we're looking for the 'best practice' means to have a new instance come online and automatically (or nearly automatically) join HAProxy.

Ideally, we'd monitor load on our systems or rely on a few years worth of analytics data to work out a rouch schedule, and when we reach a threshold or scheduled time, have a process fire up a new instance, have that new node connect to a system on our HAProxy machine to write its hostname into the config and reload HAProxy so it becomes part of the pool.

We're considering Amazon's ELB once we grow big enough to need multiple zone coverage, but until then, we need a simple setup that can add/remove machines from HAProxy.

I know there are services out there that we can pay to manage this stuff, but Scalr seems to limit us to very specific instance types, and Rightscale is too expensive, so like many others, we're looking to roll our own solution.

Unfortunately, those who roll their own solution seem to be a little hush-hush on their process.