So, I'm a complete arduino noob, and I want to start my first project. I want to read the temperatures of my CPU and GPU, but using sensors and not the software reading.
My idea is to place something like that right next to the chip, touching it. Do you think I would get reasonably accurate readings? Is there a better way or better sensor to do it?
you must know the expected temperature range to be able to select a sensor.
wrt CPU and GPU consider one that can be connect using heat conducting glue/paste.
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.
That device is most probably a DS18B20 in a weather proof package. They are available in a simpler flat-face package that would be more appropriate for your needs for about half the price. The maximum temperature for them is 120C. The performance might be a bit of an overkill for you but they are so good and easy to use, so well-suppoorted, and so cheap that you need some pretty persuasive reasons to use anything else.
Here is some background