High accuracy (0.1°C) digital temperature sensor
+/- 0.1 C accuracy is a very demanding spec. You are liable to need calibration and care.

If you use the best digital-output sensor that you can buy in your rpice range then you can seek to optimise it's calibartion and thermal equilibrium issues. If you use an analog sensor such as an LM35 you have a potentially more accurate device BUT have to fight the analog conversion demons yourself (noise, reference accuracy, stability, ,...).

The DS18S20 digital temperature sensor  has an uncalibrated 0.5C error across -10C to +85C range so it's calibrated accuracy over a few degrees C range should be much better.

If you were serious you could use something like melting Gallium as a reference with a melting temperature of about 30C and an accuracy for pure material subject mainly to second order effects.

This recent stack exchange question relates to  on attempts to get high accuracy

This one talks about calibration

The MAX6636 is probably as good as you need but the packaging is possibly poor depending on desired probe size. Multiple digital channels of lower accuracy and one internal higher accuracy.

If you are prepared to calibrate initially and ongoingly and go head to head with the denizens of analog signal conditioning you can probably use PT100, thermocouple, thermistor and more.



Added:

It has been suggested (March 2013) that the DS18B20 IC would be a better choice that the DS18S20 that I mentioned above. They say - 


According to Maxim: "The DS18B20 is recommended for any application that requires 9 to 12 bits of temperature resolution. This device offers much more flexibility and is easier to use than the DS18S20"


I agree that the B part is superior and a better choice. However ...

Great care is needed when receiving advice from companies that want to sell you things :-). I agree that the B part is superior to the S part for many purposes. It has greater flexibility in that you can do more things with the basic setup - whether that makes it easier is moot and suspect. 

BUT, neither part is really up to the job that is asked for here. Fig 16 in the S data sheet and B data sheet is identical, and shows a ~~~= +/- 0.3C accuracy to 3 sigma across 0C - 70C at any one temperature BUT a +/- 0.45C variation across the whole range. While this is commendable it is far worse than is desired. 

The B part amply demonstrates GIGO - whereas the S part has 0.5C resolution output steps, the B part has user selectable 0.5 / 0.25 / 0.125 and 0.0625 C steps (9 to 12 bits).
While these extra resolution options could in fact be useful to a designer with suitable mastery of the arcane art, they could be downright dangerous to any who tend to equate resolution and accuracy. 

So, yes, the B part is better, but still not really up to what was originally asked for.