On an unrooted phone, apps run as distinct users, and don't have access to any files created by other users or system files, i.e. they are 'sandboxed'. Since they can't make any such changes, I would say the only thing they can leave behind is a little detritus on your SD card.
On a rooted phone, an app which has been granted root access can do pretty much anything that is possible in the hardware. Apps that have root permissions can write on non-read-only storage media (including modifying the bootloader), modify other programs' private data, modify system settings, modify system files, etc. A rooted app can also hide itself from the system, and pretend to be uninstalled while being perfectly well and alive.
Basically, rooted apps can do anything that the hardware allows
Updated to include Lie Ryan's info on rooted apps.