Respuesta corta
En general, las aplicaciones se desinstala limpiamente, y la mayoría, si no todos sus datos serán eliminados. Algunas excepciones pueden, sin embargo, se aplican a sus datos almacenados en la tarjeta sd, si los hubiere.
Respuesta detallada
Android utiliza una estructura de datos que se define por los desarrolladores de la API, y los desarrolladores deben atenerse a ella. No hay demasiadas formas en que ellos pueden desviarse, como por ejemplo, permisos de sistema de archivo prevenir esto.
Aparte de la .apk (de la aplicación en sí) que se instala en un lugar definido, también hay lugares definidos para las aplicaciones de datos: Todos estos sólo se puede ir por debajo de /data/data/<package_name> en almacenamiento interno (en raras ocasiones una aplicación puede acceder a otros lugares en el almacenamiento interno para colocar sus datos, a excepción de algunos "temporal" de caché o las ubicaciones. Como para la sdcard, la API recomienda encarecidamente utilizar Android/data/<package_name> como lugar correspondiente (ver documentación del API).
Mientras los desarrolladores de adherirse a estas normas, la desinstalación de la aplicación también eliminará todos sus datos (como el sistema se encarga de todos los lugares definidos por el desarrollador de la documentación, ya que estos son fáciles de identificar mediante el nombre del paquete). Sin embargo, en la sdcard casi no existen restricciones que lugares puede acceder una aplicación (que es debido a la GRASA de sistema de archivos utilizado para estas tarjetas), y algunas aplicaciones go wild aquí.
