This remains one of my favourite hacks. It's really simple: find out what voltage is needed and then work out how many AAs are needed to make it up. The battery for my phone is rated at 3.6v, so 3 1.2v rechargable AAs was close enough. After that, the choice of battery comes down to how long you want the phone to last. My original battery was 700 mAh, so 2000 mAh batteries wired in series gives almost 3 times the battery life.
If the battery isn't labeled, use a multimeter to find the positive and negative terminals (usually on the outside). Don't just accept the first reading since the charging terminals can output current on some batteries. The ones you want will generally be the highest voltage. Note that a fully charged battery will usually give abit more than its rating. eg a 1.2v rechargeable AA will give 1.5v and a 1.5v volt alkaline will normally give 1.7-2v.
Wiring is simple. Connect the positive and negative terminals of the phone to the positive and negative terminals on the battery holder. When I did mine, I didn't do anything with the charging terminals. This meant that I had no battery life indicator. On phones where this is the case, you might be able to get it to work by putting a resister in the right place, but I don't know. I haven't tried.