1. Use high-quality NiMH cells

• You want the NiMH chemistry because it's able to supply the high peak current that leads to faster recycle times (and less energy lost to internal resistance).
• "Hold their charge when not in use" and "long lasting (on a single charge)" are opposing criteria: the reason is that the newer low-self-discharge (or "hybrid") cells have a lower capacity than standard NiMH cells (for example, the last time I was buying, you could get 2600 mAh in regular but only 2100 mAh in low-self-discharge). A rule of thumb: if the batteries are going to sit for more than a month in a ready-to-use state, get the low-self-discharge variety.
• Yes, a good brand is important, though the NiMH market is not dominated by Energizer and Duracell as the alkaline market is. Don't just buy the highest mAh - you'll get scammed. Good brands include:
  • Sanyo
  • Powerex (Maha)
  • Energizer
• Dave Etchells has written up some great capacity tests (though they are somewhat dated now).

2. Use a high-quality charger

• This is very important for cell life and capacity. It turns out that you need rather fancy circuitry and algorithms to charge NiMH cells (a) to full capacity and (b) in a way that is not damaging to them. Do not go to Target and buy whatever charger they have.
• Important qualities include:
  • Individual charging circuit for each cell.
  • Testing and refresh cycles.
  • Appropriate sensing and algorithms for charging.
• I personally use and recommend the LaCrosse BC-900, which doesn't seem to be available any more (it seems to have been replaced with the BC-9009).
• Another good brand is Maha, which has several chargers which meet the above criteria (the MH-C800 series and the MH-C9000, perhaps others).

3. Manage your battery collection

When you put four cells into the flash, the capacity of the group is limited by the weakest cell. Managing your collection minimizes this inequality. Key things to do include:

• Number your cells so you can keep track of each one. I use a Sharpie, but this wears off so I have to re-label from time to time (I label each cell twice to reduce the chance of losing the number to wear).
• Keep the cells in sets (i.e., don't just keep a pile of batteries and choose four when you need them). This exposes the members of each set to the same wear and environment, so they stay equal.
• Regularly test your cells. This will let you identify and deal with cells that are going bad (they will have diminished mAh capacity). I wrote a Python script (battman) for this purpose, but a spreadsheet will work just as well.
• Bad cells can often be repaired using the refresh cycle on your charger.
• Note that new cells sometimes have a capacity significantly lower (say 10-15%) than their rating. That's just how it is and doesn't indicate a defect. The better brands won't do this.

More info

• http://batteryuniversity.com is a great resource for learning lots more about batteries.
• http://www.thomasdistributing.com/ is my favorite retailer. Their website is a somewhat bizarre, but they have a wide selection and have provided me with excellent service. All they do is rechargeable batteries, so they actually know their products. (No affiliation, just a satisfied customer.)

(Suggestions welcome in comments - I'll edit.)