Nyquist theory for sampling data from TMP36
No matter how hard you try there will be high frequency noise on the signal that will violate nyquist theory and will alias down into the baseband. The question is how much noise do you get and how much filtering do you need to do to make it acceptable.

For the signal itself, if you go to extreme applications where the bandwidth for a special temperature sensor (that I was involved with) had to exceed 50 kHz then you have no option but to sample at above 100 kHz. We chose 200 kHz sampling on this occasion to make the design of the reconstruction filters much easier.

In most cases a few tens of Hz is fine so, make sure you sample at least 2.5 times higher than your wanted baseband signal and use as good an anti-alias filter as you can afford or justify. The faster the sampling rate above baseband the easier it is to design an anti-alias filter but, don't forget noise if you really want accuracy down to below 0.3 deg C.