OK - this turned out to be a really interesting topic. I am not an expert... until today I didn't even know that rifles were tuned. But I am a physicist, and I like to get to the bottom of things. In this case, I won't claim I am there - but I have some insights to share.
The most informative site I found is probably the description of rifle tuning on Al Varmint's website. In summary, when you fire a rifle the gun recoils, and this recoil results in a number of transverse vibrations being set up along the barrel of the gun. As far as I can tell, there will be multiple modes of vibration - the higher modes having higher frequencies, obviously. The key to the accuracy of the gun is the exact angle that the muzzle of the gun is pointing when the bullet leaves. And since the vibration of the muzzle is relatively repeatable, this means you need to get the time of flight of the bullet down the length of the gun down to the same value every time - or adjust the frequency of vibration of the barrel. It appears to me that the different methods of tuning can do either of these things.
First - a quick visual of the vibration (from the above website):
First mode of vibration:

And second mode of vibration:

For the rifle modeled, the first mode has a frequency around 80 Hz, and the second, around 439 Hz - much more than 3x higher because the barrel is rigidly held at one end, and tapers along the length.
From the above link:
ADDING A TUNER.... Adding a tuner to the muzzle of a rifle barrel does the following:
1. The additional mass reduces the amplitude of the vibrations.
2. Decreases the natural frequencies by decreasing the lower Mode's frequencies more than the higher Modes.
3. Increases the barrel's vertical end sag due to the extra weight. This would tend to make the vertical plane the preferred plane of vibration.
4. Moves the Mode 2 node closer to the muzzle.
Summarizing what then follows, the timing of the bullet exiting the barrel becomes the critical thing; you actually want to get the time when the first modes all reinforce each other, and catch the muzzle at a "stationary point" - that is, if there are small variations in the time of exit of the bullet, you don't want this to affect the direction in which the muzzle is pointing. This is probably best achieved by having the first harmonics all "point the same way".
The typical time for the bullet to travel the length of the barrel is about 1 ms; at a frequency of 100 Hz, the barrel makes the first upswing at around 2.5 ms. These numbers are not inconsistent. If the bullet is a little bit faster, you would like the muzzle to point a little less far up; and when it is slower, you want it to point a little more up. Thus, you "tune" your barrel when the muzzle is reaching the end of its upswing when a bullet of average velocity exits.
That is part one - why does tuning a rifle work at all.
Now on to part two - what is the role of temperature? Well, first I read this article about the temperature rise of rifle barrels during Olympic shooting. It concluded that at a rate of two shots per minute, the barrel temperature increased about 4 degrees, and that this did not affect accuracy. Of course, this is for a well tuned gun... It did state the coefficient of thermal expansion was about $1.2\cdot 10^{-5} / K$; furthermore, the Young's modulus of steel drops with temperature. Taken together, these effects will lower the frequency of the vibration with temperature. If you need the frequency to remain roughly constant, you will have to "shorten" the barrel a little bit as the temperature goes up - in other words, screw the tuner IN, towards the stock, with temperature.
It is hard to estimate how much the tuner needs to move, as it depends on the relative mass of the tuner and the barrel. In fact the change in length of the barrel is small: for a 60 cm (22") barrel, length changes (grows) by about 7 µm or 0.0003" for every degree C of temperature change. Since the barrel also gets wider, this expansion would actually increase the resonant frequency. However, and more importantly, the Young's modulus of steel changes by about 1% for every 35 °C, or 0.03% per degree. This means that the resonant frequency will shift down by 0.015% per degree - which might be significant.
The final piece of the puzzle is the time it takes the bullet to exit the barrel - because it's the relative timing of that with the vibration of the barrel that determines whether the gun is well tuned.
Now the question is how much the density of the air affects that time. The bullet quickly reaches supersonic velocity in the barrel - and when it does so, the air in front is compressed and a shock wave is formed. The speed of sound in air changes with temperature, so the speed of the shock wave (and thus the pressure) will depend on the initial temperature. In hotter air, pressure will be lower (speed of shock wave is higher). It is a bit late at night to do the detailed calculation... let me know if any of the above makes sense, and I might be encouraged to expand the analysis further.
Some potentially interesting things to read:
http://www.oglethorpe.edu/faculty/~j_cramer/documents/chapter1_000.doc
http://en.wikipedia.org/wiki/Internal_ballistics
http://benchrest.com/archive/index.php/t-48578.html