Is insulating an unfinished basement worth it? If so, how should I go about it?
Absolutely it's worth insulating.  

Concrete is a poor insulator.  8" concrete blocks have an R-value of 1.1 - about the same as 3/4" particleboard.

In my neck of the woods the frost line is about 3' down. So, assuming that a house here has a 40x40 foot square footprint and the basement is 8' high:

160 lineal feet x 6" = 80 square feet exposed to air;
160 lineal feet x 3' deep = 480 square feet exposed to ground above the frost line;
160 lineal feet x 4.5' deep = 720 square feet exposed to ground below the frost line.

Calculate the heat loss, using the formula (Area * (Tinside - Toutside) / (thermal_resistance) See here for a complete explanation

Assuming it's 0F outside and 70 inside (you said long and cold :) ), we'll say the above the frost line is 20F and below is 40F.

Above ground: 80*70/1.1 = 5091 BTU/hr
Frost line: 480*50/1.1 = 21818 BTU/hr
Below Frost line: 720*30/1.1 = 19636 BTU/hr
Total: 46545 BTU/hr.

Now sheath and insulate with R20 insulation.  Call it an effective R15 due to thermal bridging by the studs and because you don't do this every day so there are some gaps, etc.  Then your total comes to 3414 BTU/hr.  You save more than 16,000 BTUs/hr, or almost 400,000 BTUs/day.

In a 6 month winter that's 72 million BTUs.  

Your $ savings will depend on the price of energy in your area, what you're heating with etc.  $15/million BTUs is not unusual: that's higher than it was in Alberta where I'm from, but lower than California where I'm at now.