I used a 36V 13.8AH NiMH successfully for 7 years before it was stolen (together with the bike) and it had plenty of life left in it.
I'd avoid NiCd since Cadmium is a nasty polluting material for final disposal and the pack will weigh about twice as much as an equivalent NiMh one. NiCd calendar life may be only half as much as NiMh (my original NiCd pack was even worse than that).
Don't be tempted to swap NiMh and NiCd chargers over, the end-of-charge states are quite different in terms of the voltage 'bump' at full charge and you'll likely get under or over charging, (ie poor range or fires!) depending on which way you swap.
Unfortunately, the aviation safety business does not seem to take any note of the inherent safety differences in the various Lithium chemistries, just the total amount of Li. According to the regs, however, you may be allowed one 300Whr batt on the bike and two additional 300Whr ones, if I'm reading this right: http://safetravel.dot.gov/larger_batt.html
If that is not the case, I'd go for NiMh. I'm temporarily running a 5304 on a 36v 9AH Dcell pack, but the voltage does droop a bit under load. F cells should be fine, though heavier; count on 250g per cell, plus box weight. If you mount the cells vertically, make sure that downward shock doesn't flatten the solder tab connections into shorting out cells. Tough spacers are a must!
As to mounting, I used a TopPeak rack and my excellent local bike shop - Warlands - contacted the distributor and got both a spare slide fitting that goes under their standard trunk bag and the latch that fits on the front.
I mounted those onto a tough polycarbonate box and packed the cells - in heatshrink and foam to keep them rigid and protect the connections from vibration damage - inside with sockets. I'm also about to fit rear red LED lights powered from the main pack.
I have at least some pictures during the build, if you want.
dermot