Yes, it's an analogue device to placing a capacitor on the analogue input point will dampen the noise.
If you can analyse the noise you might be able to narrow it down to an item of equipment - and cure the problem at source.
You do not state whether or not you are using screened cable. Ideally you should be and this must be isolated from all terminals at the sensor end and connected to the analogue ground at the Arduino end. The ground wire which is connected to the LM35 should be fed as one of the cores within the screened cable.
As to capacitor size, something like a 0.1microfarad should do the job.