Ken,
The calculator at this site is a pretty good one for figuring out how many BTUs you need for heating (and cooling). If you put in your city it looks up the historical outside temps to use when calculating the load.
http://www.loadcalc.netIf your garage is attached to your house, any common walls/ceiling of the garage will effectively see zero heat loss (assuming the home is heated/air conditioned and at the same target temperature you'd like the garage to be). So, you can "trick" the calculator by putting "zero" as the square footage for any such walls/ceilings.
If you are going with electric heaters, 1 watt = 3.41 BTUs/hour. So if the calculator says it will take 15,000 BTUs to heat your garage, you'd need electric heaters totaling 4400 watts. And on 115 VAC, that's 38 amps, which is probably why you are thinking about putting in new circuits!).
One novel approach (and a project): some folks use water from their domestic hot water heater and run it through a heat exchanger in the garage (pipes and a fan). No new circuits needed, and if you have a gas water heater the utility costs will be much lower than electricity. This only works for moderate heat requirements--if you have a 35K BTU burner in the water heater and need 45K of heat for the shop, then the water in the tank will eventually get cooler even if the burner runs full time.
Getting the big garage door well sealed against air leakage is usually tricky.
Good luck!