Also, when you finally get a unit with the ability to attack more than once in turn, go out of your way to do so. You're just about guaranteed a promotion on a second victory in the same turn so I figure the odds of getting a leader might be higher too.
I agree that barracks are key. Not only do you get that veteran bonus, but you can heal up your 1 hp elite units a lot faster with 'em.
In my last game I managed to get three leaders in the same turn, rushing three wonders (UN, Manhattan, and Heroic Epic). Of course I won the next turn with the vote by some carefully planned MPPs and goading my UN opponent into war.
If you do get a leader, unless you're going to get a special tech next turn or about to make peace, I don't believe in saving them. It's much easier to get a first leader when you have none than a second one when you've got one already.