How cold or hot can my Arduino Uno get?

It's not that big of deal. The ATmega 328p datasheet states this:

Temperature range: -40 to 85 degrees celsius.

The same goes for the USB chip on the Uno (ATmega 16u2 for UNO R3).

That's inside your limits. It probably could go a bit colder than mentioned, but it'll shorten the length of the board a little bit.

However, there are some things that may go wrong:

• EEPROM might not be stored as long in extreme temperatures. Keep this in mind if you're storing critical data.
• The voltage regulator may not perform as well in hot conditions
• The crystal oscillator may not produce exact values. However, I would imagine that a few hertz more or less wouldn't affect a 16 MHz processor. The tolerance is actually a little less than 1%. You may have some issues with serial (baud rate not correct). I would look into any communications like I2C also. (I don't know exactly how the clock line works... it might be fine for I2C.)
• Resistors/capacitors may not produce the exact values. I'd imagine that the tolerance won't be more than 8% on resistors: most resistors are rated at 5% for normal temperatures. It does depend on the manufacturer. Capacitors do have a bigger tolerance, but their main purpose is to "smooth" a signal.
• Extreme cooling/warming may cause minor expansion problems. (Note: it's fine once in a while, but not on an hourly basis of dropping 30 degrees.)
• Other components (LCDs, etc.) should be kept in mind also when looking at the viability of keeping it outdoors.

So as long as all the other components not on the board will happily run in the temperatures that you need, you should be fine. Also, as with all engineering, values often have added "padding" built in. (i.e. 5% tolerance is often 3-4%, maximum 12V it can run on 12.5V, etc.)*

*_{What I mean by that is your Arduino won't explode when it's -41 degrees C. It's not great for it, but most likely you should be fine as long is it isn't a regular occurrence.}

Like everyone mentions, as long as you're in the shade, hot temperature probably doesn't matter too much as it's within the limits of the components.

I'm more worried about condensation in the mornings. Water vapors will condense on electronics just like it does on grass. You could try electrical epoxy to cover the circuit. The Arduino doesn't run very hot, so the epoxy doesn't do much in terms of preventing it from cooling down. But epoxy does keep water vapor condensation from being a problem.