How exactly does Synaptic keep track of "New in repository" packages?

Is this info part of APT cache or does it create a separate file to compare with new cache? Where is it stored then?

If I'm not mistaken the files you are looking for are:

• /var/cache/apt/pkgcache.bin
• /var/cache/apt/srcpkgcache.bin

This is a local package database for binary and source packages respectively. It is updated every time you run apt-get update or programs like Synaptic do that somehow.

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

For example:

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'