What steps are taken by the OS when an app is uninstalled?
Uninstalling an app will remove entry from /data/system/packages.xml, and delete package from:

/data/app/ (apk file)
/data/data/ (user data and cache)
/data/dalvik-cache/arm/ (translated java bytecode to executable dalvik bytecode)

Clear cache can performed from the android settings. Custom recovery twrp has option for wipe the dalvik cache.