What is the most accurate temperature sensor to use with Arduino? I know that for example LM35 sensor does not express temperature values linearly, so it doesnt provide real temperature values.
a) Accurate and linear are not the same thing.
b) I think it is hard to go wrong with the Dallas 1-Wire sensors. You can “start simple”, but you can also go on to fancier and fancier (and more and more capable) designs as your skills and wants evolve.
Dallas 1-wire are very repeatable in their measurements, however you might need to define an offset to get it callibrated. melting and boiling water are quite workable references ;)
Precision is often gained by making multiple measurements and calculate a (running) average - http://arduino.cc/playground/Main/RunningAverage - Which to use depends on your project specifications.
But you did not provide important information:
What is the most accurate temperature sensor to use with Arduino?
range - What range should it have? precision - the number of decimals? accuracy - what is the allowed difference between two samples of smae temperature? (repeatability) speed - how fast you want the measurements? ...