Why apt madison?

The madison command was added in apt 0.5.20. It produces output that's similar to a then-existing tool called madison which was used by Debian server administrators. Several of these tools had names which were common female forenames, I don't know if there's a specific history behind that.

The madison tool no longer exists but there's a partial reimplementation called madison-lite (querying a local package archive, like the original), as well as a script called rmadison in devscripts which queries remote servers.

apt-cache madison is not emphasized because most of what it displays is also available through apt-cache showpkg and apt-cache policy.

From man apt-cache:

apt-cache’s madison command attempts to mimic the output format and a subset of the functionality of the Debian archive management tool, madison. It displays available versions of a package in a tabular format. Unlike the original madison, it can only display information for the architecture for which APT has retrieved package lists (APT::Architecture)