You have to consider a lot of factors prior to sizing you battery. If you want the standard 36V using Lipo you should use 10s which would give you 37V nominal, 42Vpeak and a Low Voltage cut off around 32-30V. Lipo can be dangerous and takes special precautions like a battery monitor during use, proper charging and proper handling to prevent electrical discharge when making connections or when dropped or damaged, aka plasma.
The generic mah rating to consider is typically 1000mah/mile of ride. This can vary a lot based on grade of path/road taken, power/efficiency of bike and weight of rider.
You should look at the lipo section in the battery forum as there are many discussions on this topic there.
-rich