1. Get inspiration from the existing dialogues. Take your time and listen to them all.
2. You should get to know the personality of the leader you want to record voices for. Is he/she aggressive, pacific, etc? Prepare your dialogues starting from that. For example, in aoe3 TAD, Suleiman seemed to love food and were enthusiastic when you give food.
3. Write the lines and let everyone know and let everyone tell what do they think. When I say "everyone", I mean this forum or any website related to WoL.
4. I probably already said it, but it's going to take a long long time. It would be a waste if you abandoned at some point
5. When you think that everything is okay, record the voices in mp3 format. Make sure to make a few first, and let everyone hear your voices and tell what they think.
This will eventually be finished. When that time comes, pack all of the mp3 files in a zip or rar (or any format, but make sure it can be opened by as many people as possible) and upload the pack in your Google Drive (or any place where everyone can download it). We will make sure to properly credit you for your work