My garage is insulated 24x22, attached to the house, and stays above freezing (upper 40's, low 50's) in the coldest outside temperature without any heat.
I use this heater:
http://www.grainger.com/Grainger/items/3VU36?Pid=search.
I plug it into my TIG welder receptacle. I only turn it on when I'm in the garage, and it heats the place amazingly quickly...literally in just a few minutes.
Negligible affect to the electric bill.
Rodger