I was having issues with this last week. So I did a bunch of research both here and elsewhere and here's what I found.
1. Be sure your GP system is functioning correctly. My truck is bone stock in this regard. Original GP solenoid/relay on the firewall, factory control card and military plugs (Wellman 070). They function flawlessly at sub-zero temps. A few are getting crispy looking (blackened around the nut- probably from the morning I had to cycle them 3x before I figured out it was a battery issue), but they still all show proper resistance on the ohm-meter. I'll probably change them out in the next couple weeks.
2. Be sure your batteries are properly conditioned and fully charged. This is where I had problems. I only have a 1.3 mile drive to work, and I come home for lunch. This adds up to draining the batteries pretty quickly, and a fair amount of strain on the engine. As another member pointed out, it's leaving a diesel oil mix in the engine. The batteries should have a good 10-15 minutes minimum time of being recharged by the alts after each start. You can buy a charger/jump-starter/reconditioner at Home Depot for around $70. The reconditioning mode "desulfates" the battery [if you leave a battery sitting, the lead sulfate builds up on the plates and keeps it from holding a full charge] with a 24-hour charging cycle.
3. Be sure you're letting the engine get and stay warm if it has to sit in the cold for a few hours or more. Let the high-idle kick down before driving to ensure your engine is warm enough to avoid unnecessary wear. This should give you at least 5 min of idling/charging, or more if the temps are really cold. The coldest day it took a good 8 minutes before it kicked down. Some folks recommend using a lighter weight oil or a synthetic, as synthetic has a lower gel point. I'm using 15W40 non-synthetic.
4. Get a block heater of some sort. Avoid the dipstick heater. It's a complete waste of time and money. Although Kats makes good heaters, their dipsticks are worthless. When they work they can add an effective temp increase of about 10-15 degrees. They're only rated for something like 90 watts. Problem with them is only about 1 out of any 10 you might buy actually work. Most of them burn out their own circuits the first time you use them. $20 down the drain (i got a refund). NAPA sells a magnetic oil pan heater from Kats rated at something like 600 watt. This isn't bad for keeping the oil pan warm. They go for about $30. I'd recommend taking it off before driving around, though. The magnets aren't that strong. Another option is an in-line heater that you install in your lower radiator hose. These seem to do pretty well for most folks and are pretty easy to install, but your results may vary. The time-tested OEM proven method is a freeze plug heater. These install by removing a freeze plug from the engine and inserting them in it's place. Installation isn't too bad, but removing the old corroded freeze plug can be a royal pain, especially if it's awkwardly located and it's already bitterly cold outside. Some guys will even insert one in each side of the engine. This has actually be proven to lessen uneven engine wear. So, if you have $130, a freeze plug heater, combined with a magnetic oil pan heater and a battery charger/starter/re-conditioner, and you should be able to start at -40*F. Cheaper than getting fired for being late to work.
5. So far, keeping my engine warmed and batteries charged (idling/charging at least 15 minutes for each start) has allowed me to start the truck at -10*F this season without too much coughing up of white smoke. On the coldest night I put the batteries on the charger and then had the charger standing by in jump-start mode the next morning. Fortunately I didn't need it.
6. Park in a heated garage.