Are internal combustion engines more efficient on cold days? According to Carnot efficiency formula $\eta=1-T_C/T_H$, can we say that the engines of cars are more efficient on cold days where $T_C$ (the temperature of the surroundings) is less than on hot days? 
 A: A car engine uses (approximately) a cycle called the Otto cycle, but this is close enough to a Carnot cycle that the same concepts apply. The hot temperature is the temperature of the gases after detonation, and the cold temperature is the temperature of the gases when they stop doing work i.e. when the exhaust valve opens and the gases exit the cylinder. It is not the external temperature. This is what I assume dmckee is alluding to in his comment, though I don't recommend touching the exhaust pipe right by the exhaust valve as the screaming noise is distracting.
In principle the external temperature has some effect because if the engine pulls in cold air the post detonation temperature will presumably be slightly lower. In practice I suspect engine management systems compensate for this. Anyhow, to a first approximation the external temperature does not affect the thermodynamic efficiency of a car engine.
A: The efficiency of the engine is limited by the ratio of the two temperatures, I.e. your ability to extract work from that temperature difference. However, most people are interested in fuel efficiency, and here you have to consider how much energy has to go into creating that temperature difference, not just how much work can be extracted from it. So on very cold days, a lot of fuel is used just to combat heat loss through conduction, as well as to bring the reagents up to combustion temperature (here the free energy is important). Lower temperatures also lead to incomplete combustion. The only saving grace is that the inlet air is denser so provides more oxygen, but I don't know how big that effect is.
A: The actual efficiency of the engine is most likely not driven by the "outlet temperature" but by the viscosity of the lubricants. On a cold day an engine has to work a lot harder to move the oil, and this will definitely affect (negatively) the efficiency - at least until the engine heats up.
Next, the temperature at the hot part of the cycle will be lower since the same amount of fuel heats the intake air to a lower final temperature (it starts at a lower temperature). This is the point that Kieran made.
Finally, the engine doesn't "give off heat" at the end of the cycle - rather, it releases the exhaust gases at the end of the compression stroke, when they still have a significant pressure. The change in volume is the same, but the initial pressure is lower (since the gas started out cooler). This means that the work done per stroke will be less. I think this is actually the most important aspect in this case.
I conclude that an ordinary internal combustion engine would be less efficient at lower temperatures. And where I live, I certainly get significantly less mileage from my car in winter (but there are many other factors contributing - not just thermodynamics).
A: There are a lot factors involved here, but as internal combustion engines follow the Otto or Diesel cycle, those cycles (which are less efficient than the Carnot cycle) are the right model to follow, rather than the Carnot cycle itself.
Let's say we reduce the inlet air temperature from 300 Kelvin to 270 Kelvin (90%) while keeping compression ratio and RPM the same. 
Now, the engine ingests the same volume of air, but greater mass. This means that a greater mass of fuel will be needed and greater power will be produced.
The compression step remains the same, that is, if before it doubled the temperature from 300K to 600K, it will now double the temperature from 270K to 540K. The combustion chamber pressure before ignition will also be the same.
The burning of the fuel will now increase the temperature by a fixed amount, so in the  first case it will reach 600+2000=2600K and in the second case it will reach 540+2000=2540K.
Expansion will now half the temperature (assuming reversibility and neglecting the minor change in composition of the gas during combustion) so the exhaust temperatures are 1300K and 1270K.
What we can see from this theoretical internal combustion engine cycle is that the efficiency of both compression and expansion is determined only by the compression ratio. But also note that a significant proportion of the energy generated in the expansion is needed to drive the compression. The proportion is marginally less at lower temperature (due to the fixed temperature increase provided by combustion) so the engine will theoretically run slightly more efficiently at lower temperature. 
For identical efficiency, we would need the fuel to increase the temperature by 2000K in the 300K ambient case and 1800K in the 270K ambient case. But as the temperature increase from combustion is independent of the ambient temperature, the lower ambient temperature gives higher efficiency, at least in theory.

There are many practical factors that may affect this analysis. The first is that my exhaust temperatures are extremely high. I can assure you that a temperature increase of 2000K is typical for complete combustion of hydrocarbon in air (I am a boiler engineer, but here's a table for those who like to check http://en.wikipedia.org/wiki/Adiabatic_flame_temperature.) Reciprocating internal combustion engines do run at close to complete combustion of all the air ingested, so it would appear that there are significant losses to the cooling system during the combustion process.
My own experience is more with industrial gas turbines, which have proportionally much less loss to cooling systems, and an exhaust temperature arount 800K. Gas turbines never burn sufficient fuel to use all the oxygen in the inlet air, because the expansion turbine would melt. If suitable materials were available they would use all the oxygen, which would make them a lot more efficient.
The next thing to consider is the valve timing. It will be apparent that if we have the same ratio on the compression and expansion stroke, we have effectively the same mass of gas entering the engine at 270-300K and leaving it at a higher temperature. The higher temperature means there is a higher pressure at the end of the expansion stroke, and if the exhaust valve opens too early, about 2-3 bar absolute (1-2 bar gauge) of pressure will be wasted. Although there are from time to time suggestions of ways to improve this situation, including closing the inlet valve late (to reduce compression) and opening the exhaust valve late (to increase the expansion) this is not a common pattern of operation. One reason is that when there is only 1-2 bar gauge pressure left, the amount of friction means that not much shaft power can be usefully extracted. However modern engines are often able to vary their valve timing and this complicates real-world analysis considerably.
Thirdly, as per the above analysis an engine will produce more power in colder conditions due to the greater mass of air ingested. If more power is produced and friction stays the same, we would expect a small gain in engine efficiency, too.
Finally, let us consider turbocharged engines. Here the pressure in the exhaust gas which would otherwise be wasted is used to drive a turbine, which compresses the air at the engine inlet. The primary motive for this is to increase power by increasing the mass flow into the engine. The work of compression heats the inlet air, so an intercooler is installed between the turbocharger and the engine. The purpose of this is to cool the air back down to ambient to further increase the mass flow of air into the engine.
In conclusion, colder conditions produce a measurable increase in engine power (otherwise intercoolers would not be installed on turbo engines.) According to a theoretical cycle analysis they also produce an increase in efficency, though this is likely too small to be measurable, and may be negated or reversed by other factors. 
A number of people continue to believe colder temperatures lead to worse mpg. This is generally true for a variety of reasons: Cold temperatures lead to lower air pressure in tires, wet roads have increased resistance, cold temperatures lead to thicker lubricants etc. The engine is operating more efficiently (unless we choose to disbelieve 1-Tc/Th) but is working against a host of conditions, that lead to reduced mileage, that occur during the winter. Try picking a spot of road you drive every day. Put your car in neutral at a given speed at a given point. You will coast farther during the summer, with your engine disengaged. 
A: Internal combustion engines aren't Carnot engines, but they operate on a similar thermodynamic principle, so for the sake of this question, let's say they are.
$T_\textrm{H}$ is reached by adding thermal energy from the combustion to $T_\textrm{C}$, the temperature of the inflow. The energy produced by combusting a giving volume of octane is fixed (assuming you do it efficiently, it depends only on chemical properties of octane, oxygen, carbon dioxide, and water), adding $\Delta T$ to a given volume of inflow. Thus we can write $T_\textrm{H} = T_\textrm{C} + \Delta T$, and then rewrite the efficiency as:
$$
\eta = 1-\frac{T_\textrm{C}}{T_\textrm{C} + \Delta T}
$$
For fixed $\Delta T$, we see that $\eta$ decreases as $T_\textrm{C}$ increases - however, around standard operating temperatures, this difference will be quite small!
A: For engines with oxygen sensors (Lambda sensors), the exhaust is kept at a very low oxygen concentration. As such, if the air ingested is not heated enough they pull more air (by mass) in the same volume (engine displacement) so they consume more fuel idling.
Also, during winter I start my car early so have heat on windscreen (so it won't freeze on the way), and this also negatively affects the mpg.
 Other reasons why fuel efficiency during winter might be lower is the increased rolling resistance when running in the snow/mush, keeping engine in a lower gear to have improved engine braking, reduced overall speed.
   So while engines might be more efficient in winter, cars (overall) usually aren't.
