How does the Software Center keep track of packages?
How does the Software Center keep track of installed packages? In which files/database?
dpkg (Software-Center is a graphical front-end of dpkg) keeps track of the installed packages in /var/lib/dpkg/status.
From what I can tell, it uses xapian databases located at /var/cache/software-center/xapian.
From a quick read over the code here, specifically the 'rebuild_database' function, it looks like the above are built/re-built from the apt cache (using the Python-apt wrapper, which in turn uses libapt-pkg).