What classifies an application as 'installed' in Ubuntu?
Solution 1:
dpkg, through apt or aptitude keeps a database of the installed software in /var/lib/dpkg/status.
You can learn more about this here.
My response is based on a response given in this forum discussion.
As @psusi pointed out, because apt and aptitude are merely front-ends to dpkg, it is actually dpkg that keeps track of packaging.