AVcc, and capacitor, using ADC
I will first talk about decoupling capacitors, and then specifically the options the Atmel 328P has for it's AVCC and AREF pins. 

Decoupling capacitors are used to provide short bursts of energy during digital switching circuits (they go from zero to full voltage in a very short amount of time, they need energy and available current source nearby to do this) and as a general value everybody just puts 100nF (0.1uF) capacitors at the power pins of every single IC used in their boards. This is a safe and good strategy. It is not, however, strictly needed unless your system is large and complex. If you have a regulator (with it's own capacitors) very close to your Atmega you will be fine with out them. 

Your regulator is fine with a 10uF capacitor on the input and output, you do not need to change those. In the future though, you should ALWAYS consult your regulator's datasheet. Some regulators cannot use high "ESR" capacitors as they can cause unstable operation, and likewise some regulators cannot handle ultra-low ESR capacitors like Ceramic capacitors because they will "ring" and ripple uncontrollably (overshoot constantly) among other hilarious power control system challenges. 

AVCC is the analog voltage supply used internally by the ADC and is most commonly internally connected to the AREF pin, used directly as the reference for ADC readings. You can either filter and decouple AREF, or VCC, but the one that matters most depends on what you actually want for your ADC. The Atmel328P has internal Vref (2.56V or other ones) you can select, for exampl. You can also provide your own reference voltage at the AREF pin, and other than power supply ripple your AVCC becomes less important in terms of filtering. You might have bought a precision 3V reference IC, and followed it's datasheet guidelines for suggested circuit, and then put the Vout into the AREF pin of the AVR. In this case, AVCC can be left with either: 


direct connection to VCC
or a simple decouple 0.1uF cap to help with local noise filtering
with an inductor or ferrite bead in series from VCC into the AVCC for AC current ripples, and if you put a capacitor to ground here as well (AFTER the inductor), it becomes a current AND voltage ripple filter - nice and clean!


AREF could be left unconnected, and merely filter VCC. Often if the AREF pin is un-used and AVCC And AREF are internally connected, you can put a 0.1uF capacitor on the AREF pin, which will have the same effect as putting the capacitor on AVCC due to the internal connection. Maybe this can assist with circuit layout?

If you have a slow, steady state error on your temperature sensor, I bet you it's not related at all to ADC or power supply filtering - I bet that the error is within tolerances given by the datasheet (usually +-15% which is quite a lot!). You almost always need to (usually only once) 'calibrate' your ADC readings by getting a known (working) thermometer at ambient temperature nearby, and adjust the offset of readings to make it line up with expectations. The sensor's rate of change (mV/Degrees celcius) should still be fine, it's just the 'steady state error' inherent to low tolerance manufacturing.