I'm going to be referring to an old AvWeb article by Mike Busch with my links in this post.
As with most of what Mike writes, it's worth a good read.
Why is Pre-Heating Important?
Pre-heating your engine in the winter is important for a bunch of reasons, but there are two main ones that should get your attention - the first is preventing metal-on-metal wear by ensuring all parts have adequate clearances to function, and the second is improving lubrication by making sure your oil is ready to flow, and the spaces it's going to flow in to are opened up enough to let the oil in.
Metal-on-Metal Wear
Starting a piston engine is responsible for most of the wear the engine sees in its life - surfaces which have long since had their protective coatings of oil drip off are banging together while you crank the engine, and for a few seconds after startup until the oil pump can build up pressure and splash lubrication in the crank case can thoroughly coat the other moving parts.
In the case of a truly cold start there's an additional complication: like 2NinerRomeo points out, different metals in your engine have different coefficients of thermal expansion, and you have steel (probably several alloys), aluminum, brass, and a few others in your powerplant. When cold the clearances between these metals can be so tight that the additional wear is substantial, and at a certain point you may even damage the engine by attempting a start, shaving or spinning bearings and scuffing cylinder walls with the rapidly expanding pistons once the engine fires.
Lubrication
The other factor to consider in a cold start is lubrication - both the oil doing the lubricating, and the spaces into which it needs to flow.
Take the dipstick out of a cold engine and you will marvel at how the oil just clings there in a thick layer (this is especially true of heavy single-grade oil like 100W, but even 15W50 starts getting very sticky down in the 30°F-35°F range). Oil that has thickened up from the cold doesn't pump very well - your engine may take a longer than normal time to develop oil pressure, and narrow spaces may get little to no lubrication until the oil has heated (and thinned) enough to get through the narrower oil galleys and tight spaces between some components.
Those tight spaces, as I mentioned under Metal-on-Metal Wear, tend to be tighter when it's cold, which means it's even harder for oil to work its way in and build up a good film of fluid. Until that film is built up and doing its job your engine is really inadequately lubricated, even if it's running. (Check out the webinar video in 2NinerRomeo's answer where Mike Busch goes into a lot of detail on how oil works, he has a nice explanation of the fluid film lubrication process.)
How do I make sure I do my preheat right?
The best preheat possible is spending the night in a nice, warm, heated hangar. It basically guarantees that every part of your aircraft has been brought up to the same temperature, and even affords you a nice place to preflight as opposed to doing it out on the ramp in the 6-but-feels-like-60 knot winter winds.
A hangar preheat isn't just the best for your engine -- your gyro instruments get brought up to a nice warm temperature (remember, mechanical gyros have to spin up, and they have the same issues as your engine did in terms of clearances being reduced by the cold), and the ship's battery gets warmed up too so it's ready to provide its best possible cranking current.
I don't have a hangar you insensitive clod!
Unfortunately some of us (like ME) don't have hangars - heated or otherwise - or our local FBO charges a hefty sum to spend the night in the warm. Those of us without hangars have to make due with a ramp pre-heat of some kind. I'm going to assume you're in the same boat as me (no hangar, no electricity), and have to use some other technique.
Most ramp pre-heats where you have neither a hangar nor electricity take the form of a "forced hot air" system - either one wheeled around by the FBO, or portable ones powered by propane. There are even ones built around a camp stove which are deceptively good at the job (and in a pinch can burn the avgas you drained checking your tanks for water).
The general procedure for a forced-hot-air preheat is to point the heat into the cowl's cooling inlets, letting the warm air flow over and around the engine and out the cooling outlets. Start the heater up before your preflight, and with a little luck by the time you're done with the walk-around your engine will be ready to start.
If it's extremely cold you may want to block part of the inlets and put a blanket over the cowling during the pre-heat to help keep the heat trapped on the engine, and as 2NinerRomeo points out, when using a high-intensity heat source like a propane heater make sure you don't pump so much heat into the cowling that you blister your paint. A gradual warm-up is what you want - we're slow-roasting the engine, not broiling it.
How do I know the preheat is "done"?
There are three common ways to tell if your preheat has had enough time to adequately warm your engine - each technique works pretty well, and you can use whichever makes the most sense for your situation.
Testing by feel
This is classic if you have a cowling that can be easily opened like most Piper aircraft, just feel all of your cylinders and the crankcase. They should, if your preheat was thorough enough, all be slightly warm to the touch. It's low-tech, but it works well if you can use it.
As a practical matter it's usually easier to tell if the "top end" (cylinders) are ready this way than it is the "bottom end" crank case / crankshaft / bearings), but with some cowlings (many Cessnas, or my Cherokee 180) you're simply not getting your hand in there to feel the engine: you can reach the front cylinders and a bit of the case, but the aft half of the engine is basically inaccessible without taking the cowling apart (and losing all that trapped heat).
Testing with the dipstick
Another good indicator is that when you take the dipstick out of the engine the oil flows off nicely -- compare with how thick and syrupy the oil was in the cold engine and is should be obvious when it's "ready".
This works for pretty much every engine, even if the only access you have is the little oil door, but it's also one of the slowest & most conservative indicators: pretty much all the thermal mass of the engine needs to heat up before the oil in the sump is going to get warmed up and start to loosen up.
Checking with your instruments
The final way to check the status of your preheat is to check your engine instruments: If your cylinder head temperatures are all reading something reasonable (say 60-70F) and your oil temperature is at least "off the peg" your engine has been thoroughly heated.
This technique is a little instrumentation-dependent though -- some engines may not show an oil temperature indication until you get your oil up into the 90 degree range (which would be great for start-up, but lousy for sitting on the ramp waiting). For those engines you probably want to use the dip stick test to check if the oil is "ready".
This technique also works best if you have individual cylinder probes, as you can determine if your engine has been evenly heated (this is especially true of longer engines, like a 6-cylinder powerplant: if the front cylinders have been getting blasted with warm air and are in the 90s, but the rear cylinders are still reading 30 degrees you may need to adjust your preheat procedure to warm those rear cylinders!)
Parting Thoughts - Stuff outside the engine compartment?
I've concentrated mostly on pre-heating the engine, which is what most people think about when they think about pre-heating aircraft, but as I mentioned briefly it's worth noting that other parts of the aircraft benefit from pre-heating too.
For example, a warm battery (60-70°F) will crank better than a cold one. If your battery is in the engine compartment it will get warmed up during your preheat, otherwise you should be aware that cold starting puts a pretty heavy demand on the battery, and your battery will appreciate if you limit cranking as much as practical.
Similarly, your gyro instruments (turn & bank, directional gyro, attitude indicator) will all need to spin up - that happens in a hurry (as soon as you hit the master for the electric ones, as soon as the engine catches and the vacuum pump starts really spinning for the vacuum driven ones).
If you can direct some warm air into the cabin your gyro instruments will thank you (and you'll probably thank yourself - those control yokes are COLD!). The gyros take less of a beating than your engine, and certainly cost less to replace when they wear out, but keeping them happy is worth a little effort.
