I am using Android 6.0.1 though i'm not sure that would make a difference with my question. So my question is after an app has been uninstalled through Settings --> Apps and then clicking the "Uninstall" button after selecting the particular app is there, in general, any evidence left on the phone that the app was ever installed? Secondly, if so how can that evidence be removed? Sort of like how a browser has a "browser history" after you've visited sites is there anything analogous in a history or a cache of some sort that can be recovered to see that the app was once on the phone and OS (barring a sophisticated forensic analysis). If i were to hand the phone to someone who is tech savvy or knows their way around android would they be able to ascertain that the app was once there?
Basically yes, any kind of data erased from a memory can be recovered since the space is "marked" as empty so new datas can be overwritten over them. Those datas can be easily recovered with software like Recuva or more advanced forensic tools. You need to overwrite them with a third-party software.
On Android this can be achieved with apps like Secure Eraser. ( This kind of applications can not guarantee 100% that the data have been permanently erased)
Also remember that a list of the applications downloaded from Google Play is available on GPlay app under the App > My Apps tab. You can also see them from a web browser on this page after logging-in to your Google Account.