AVCC is internally isolated from the VCC terminal, and needs to be within a diode drop of it. The idea is to isolate it from the main logic power supply, and decouple it to the local analog ground. The usual point is to make sure the analog ground plane is tied to the logic ground plane to prevent current loops from the logic. But if you want to connect it directly, go right ahead.
AREF needs to be decoupled to ground - one of the ADC settings is to enable the 2.5V "reference" and put it on the AREF pin, but it still needs some capacitance. (BTW, check the specs of the "reference" and make sure it is tight enough - many people laugh when they see its "specs").
Nigel's right - If you have a negative power supply, then you'll need to figure out how to push it above ground - just put a (biased) diode in series with the LM35's ground pin. This will let you see "-.6V" worth of signal, at the expense of the upper side of the rail.