This information is managed by launchpad.net.
You could write a script to search for a package on that site, and parse the resulting web page, screen-scraping style, to get to the release date. E.g. if you are looking for the package logrotate, the page would be https://launchpad.net/ubuntu/+source/logrotate and the release date is on the line starting with Xenial Xerus.
A more elegant solution is to use the API. This page describes all you can do with the API. I haven't used it myself, but it looks like it lets you query any object from the database.
EDIT
I played around with the API for a bit. The following piece of Python code gives the release date/time of the package logrotate for the xenial distribution series:
from launchpadlib.launchpad import Launchpad
launchpad = Launchpad.login_with('hello-world', 'production')
ubuntu = launchpad.distributions["ubuntu"]
archive = ubuntu.main_archive
series = ubuntu.current_series
print archive.getPublishedSources(exact_match=True, source_name="logrotate",
distro_series=ubuntu.getSeries(name_or_version="xenial"))[0].date_published
In order for this to work, you need to have the package python-launchpadlib installed. You also need to have a Ubuntu One-account with which you log into Launchpad. On the first run, the program will open a browser to let you give the program permission to access Launchpad.