As far it goes for DS18s20, look at
http://stuff.nekhbet.ro/2009/08/23/how-to-use-the-ds18s20-and-ds18b20-temperature-sensors-with-arduino.html
and ongoing topic about protecting it from moisture
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1290802591/7#7
Good point to DS18s20 would be that u dont have to worry about supply voltage droping over time, the datasheet says it works down to 3V. The bad thing here is that the program on that page takes up to 5310bytes, u could make it a bit less, but not much. 1 good point is also as u need 2 sensors you will need just 1 input for both sensor, but i dont think that rly mathers to you 
- Analog TMP36/LM335 -- they are easier to use (just read from ADC), but what to do with AREF? MCU is powered from 3 AA batteries, so reference voltage will be not stable.
I didnt work with those 2 yet, because the local suplier doesnt have them. If u have to measure only positive temperature then pick LM35DZ. Why?
Because its easy to use...
Take a look at code and there are some interesting coments as to what to do with the analog value.
In ur case as they measure negative volatage and because of that u have offset voltage and diffrent voltage range not like the LM35DZ which has 0-1V for 0-100 degrees Celsius and because of that u can even pick internal referece volatage of 1.1V.
But the links do explain how to use the analog reading u just have to change it, so it suits you.
Btw i am sure there are plenty examples with TMP36 if u google it up.