Recently when I was looking for temperature sensor for my mobile robot i found very small and inexpensive module BME280. This tiny sensor is capable of measuring up to three physical quantities: temperature, humidity, pressure/altitude. Its operating temperature range is quite wide: -40C to 85C. It is very energy efficient sensor - it takes measurements at less than 1mA and in a sleep mode less than 1µA. The easiest way to connect this sensor to the Arduino is by using The I2C bus (you do not need a voltage converter as in the case of SPI). You just need to connect four wires:

Measurement data can be stored on the micro SD card (you need to connect external micro SD card breakout to your Arduino Mega 2560). I prepared for you a simple program logging measurement data on the SD card.

Below you can see some charts of measurements taken with the BME280 sensor. The relative humidity can be measured in a range 0 - 100% RH and pressure 30 - 110 kPa.