I picked up a nice compact little temperature and relative humidity sensor called the RHT03 for a project from Little Bird Electronics. It and very similar parts appear to go by the names RHT-22, DHT-22 and AM2302. You can find the part at SparkFun, Adafruit, etc too.
It took a lot more work to get it working than I expected, so I thought I'd write it up here for anyone else who is looking into it. There's sample code at the end of this post, but you should probably read the details because this is a quirky beast.
UPDATE: I since found a library on GitHub: nethoncho/Arduino-DHT22 that does a better job more simply and compactly. It works fine with my sensor. It needed some changes for Arduino 1.0 and some further tweaks to work how I wanted, so I've uploaded a fork here: https://github.com/ringerc/Arduino-DHT22.