Temperature Sensor - Arduino Noob

The smaller the sensor the better. With a big sensor like that probe you have two problems: 1) the response time will be very long for something with a small thermal mass like a CPU or GPU; and 2) you can only afford a small contact area and much of the sensor will be exposed to free air, to the reading will be somewhere between the temperature of the chip and the air. I have used 0402 sized surface mount NTC thermistors to measure the temperature of power LEDs, but I needed a microscope to solder the leads! Take a look at something like the Epcos B57861S103F40, available from Farnell in Europe and Newark in the USA.