Accurately measuring temperature with Arduino

I think you should consider using a digital temperature sensor like DS18B20/ DS18S20 because it does not depend on the accuracy of your ATmega ADC to measure an anaolg signal, it uses 1-wire digital protocol to report temperature.

Refer to the following tutorials
http://playground.arduino.cc/Learning/OneWire
http://www.hobbytronics.co.uk/ds18b20-arduino

Your measurement will be as good as reference voltage for ADC is good. Arduino by default uses supply voltage as reference voltage, but in your case the right way to do it would be to use Aref pin of arduino. You have to get a special chip called "Voltage reference" and connect it to Aref pin, then set ADC to use the external reference in Arduino code (analogReference(EXTERNAL))

The voltage of the reference has to be selected so that the full swing of your temperature sensor will fit into referece voltage. TMP36 will output ~1.5V @ 100C, so you would have to use reference above 1.5V for measuring temperature up to 100C. You want your reference as close to the maximum voltage measured as possible to get as much resolution as possible.

Atmega328p has two internal references that can be used without any external components. One is 1.1V, another 2.56V. They usually are a bit worse accuracy than what you would get by using external dedicated component. Check Arduino documentation for analogReference and Atmega328p datasheet for internal reference accuracy.

If you really want to get nuts with different ranges, you can use several external references and switch them by using an analog switch like 74hc4051. Or you can switch between two internal references.

With thermistors you will have better results if you set up a constant current source instead using a dumb resistor. On another hand - a dumb resistor powered from a stable voltage reference would work ok.

When choosing an external reference, make sure you have enough voltage to accomodate for it's drop out voltage when powering from batteries and the batteries are flat. Vref+Vdropout < Vbat-min.

It seems you are aware of the problem with the reference voltage changing and if you use a device like the TMP36 (fixed 10mV/degC) there is nothing you can do other than use a voltage reference from a chip to stabilize things.

However, if you are using an RTD or a thermistor then the problem won't arise. You ADC is making a ratiometric measurement - it compares the ADC input to its reference voltage BUT, if you power the RTD or thermistor (via a suitable resistor) from the same ref voltage it won't affect readings. If the ref goes up 10% then so does the voltage into the ADC.