The +/-0.5°C accuracy is guaranteed across the -10°C to +85°C temperature range, and includes error for ADC and any drift over time (which is negligible). 

Maxim uses two matched transistors with a known voltage differential behavior across temperature. We trim the ADC to generate a digital temperature value corresponding to the known voltage behavior across temperature. So like the curves in Figure 17 of the datasheet, all DS18B20's will have that signature curve. The ADC trim adjusts that curve so that it falls within the +/-0.5°C limits. The resolution determines how many samples of the voltage we take and average, but does not affect the accuracy of that measurement, just the number of bits we report back.

The the accuracy is always +/-0.5°C regardless of the resolution.