Welcome to the forum!
It is very normal that the LSB's of the ADC are susceptible to random variations. Assuming a reference voltage of 5V, at 10 bits you're down to less than 5 mV to trip the LSB. This can be easily caused by EMI noise, like fluorescent lights etc.
The easiest solution is to put a capacitor in parallel with the LM35 output, or even an RC filter if you don't mind a little calibration. This will flatten the noise on the line.
Another option is to keep the line between ADC and LM35 as short as possible to avoid picking up noise. Of course, don't put it too close to power components (i.e. switching regulators) because their heat dissipation will influence the LM35.
And finally, you can of course also discard the LSB's, if you can live with a lower accuracy. This is the hardware equivalent of calculating a moving average on the FPGA.