Most electronics will work fine around 0 degrees F. The ATmega chip is rated to -40 degrees C*. But, I wouldn't trust the "average" LCD, and batteries don't usually work "perfectly" when cold either.
A Mini-heater should be easy to build. You can just use resistors (probably 2W resistors or bigger... 10W (or more) resistors are common too, so it wouldn't be hard to make a 100W heater.. All of the power dissipated in a resistor is converted to heat.
The hard part is calculating how much power you need. If you have a small insulated box, less than 10W will probably be enough... You'll probably just have to experiment to see what kind of heat-rise you can get. In case you don't know, you can calculate power (Watts) as Voltage squared divided by resistance. (And, the power dissipated in parallel resistors simply sums-up.) As a rule-of-thumb, you should use a resistor rated at twice the actual continuous-power.
Since this thing is apparently battery powered, all of the power is going to come from your battery! The heater is most-likely going to take more power than the circuit.
Are you going to run the heater full-time, or will you have a temperaure sensor and turn it on only when needed?
* WOW! I just realized that -40 is an "interesting" number when converting between Fahrenheit and Centegrade!