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 could do more or less anything - all bets are off :-)