Is this info part of APT cache or does it create a separate file to compare with new cache? Where is it stored then?
To extract the information from the apt cache, you use
apt-cache or other Debian/Ubuntu tools such as aptitude. For instructions and examples, see
man apt-cache or the Debian Package Management manuals
apt-cache show software-center
will list the complete package information.
Synaptic is essentially a GUI wrapper around apt, so its apt that is keeping track of the repository and package information and Synaptic is querying it.
apt-cache wrapped in bash scripts is probably the easiest way to do something similar on your own. Synaptic uses libapt-pkg* via C++, but there are also libraries for Perl and Python.
Finding new packages in aptitude
aptitude search '~N'