Temperature sensors for an Arduino sous-vide project
Get a precision temperature sensor IC, like the LM35CAZ.



You power it with a good 5v, and the output is a simple voltage which is a linear function of temperature. They have a pretty good accuracy of ±1⁄4˚C
at room temperature.

Added:

Several people have talked about "Accuracy over temperature range" for this sensor being ±1ºC. This is the wrong range to talk about. "Accuracy at cooking temperature" is the right range to talk about. At about 60ºC accuracy is ±0.7, and probably better than that. The 'typical' line varies by about 0.1ºC over your cooking range.



You probably only need one or two calibration points to get this sensor easily accurate enough for your needs. But, of course, that requires an accurate thermometer to calibrate it against. For that, you have a couple of options:

Option 1: You can use water. The temperature of water that's undergoing freezing is 0ºC. So stick it in a small cup of water in the freezer, and watch the output voltage carefully. It will fall and fall until the water begins to freeze. At this point, the temperature will stop falling and stay flat for a little while. Once freezing is complete, the temperature will begin to fall again. Take note of the voltage in the flat region to use as your 0ºC calibration point.



Do the same for boiling water. It's best to do this at sea level. If you're not at sea level, then check what the water boiling temperature is at your altitude.



Using 0ºC and 100ºC isn't as good as using, say 50ºC and 80ºC, but it's a lot easier. If you do have a very accurate thermometer available, then you should use calibration points closer to your cooking temperature.

Option 2: Use methyl alcohol. (Thanks stevenvh) This boils at 64.7ºC. This is so close to your cooking temperature, that you should only need one calibration point to get a very accurate cooking temperature. Obviously be careful not to intoxicate or blow your self up with the fumes. Don't heat the alcohol over a naked flame!

Added - Amplification

Since you're working in a narrow temperature range, and you need good control accuracy, it's probably also worth amplifying the output of the sensor. This will give greater ADC resolution at the Arduino, which will translate into better stability of the PID control algorithm. See the question Analog voltage level conversion (level shift) which discusses amplifying and level shifting an analog voltage.

Assuming you're working in the 40ºC - 100ºC range (0.4v - 1.0v). You'll want to subtract 0.4v from the signal, giving 0.0v - 0.6v, and amplify the result with a gain of 8, giving 0.0v - 4.8v. This will give excellent resolution.