For Lithium batteries, colder is generally better. Thus the suggestion to refrigerate unused Lithium batteries.
http://www.thunder-sky.com/pdf/TS-LFP40.pdf
Thundersky specifies a minimum *operating* temperature of -45C or -49F. (It does not specify the minimum storage temperature, so just assume it's the same as the minimum operating temperature.) So it looks like Lithium is the way to go for cold climates.
It should be very easy to make a battery heater from old electric blankets. Just take out the resistance wire (which I think would be insulated in plastic so sweat cannot cause current leakage) and string it between the batteries.