@FaheemMitha already gave a perfect answer for Debian, but I wanted to add the process for Ubuntu. If a package is included in Debian, it will automatically be included in Ubuntu shortly down the road:
Ubuntu regularly incorporates source packages from Debian, so it is encouraged to upload a package to Debian first to automatically have it in Ubuntu in due time. In addition to that your package will reach a much broader audience if it is in Debian and all of its derivatives.
You are also recommended to file a bug with Ubuntu's LaunchPad to move the process along faster.
Packages that have recently been added to Debian unstable will be automatically synced into Ubuntu prior to the Debian Import Freeze (DIF). After the Debian Import Freeze, you will have to file a bug with the summary field "Please sync from debian " where is the package you would like to see. Find the date for Debian Import Freeze on the release schedule page.
Fedora's process also involves filing a ticket. For CentOS, the process is here and is done primarily through a mailing list.
For OpenSUSE, see this guide.
Amazon does not seem to provide a guide for Amazon Linux, but getting it into CentOS and Fedora should get Amazon to pick it up after a while.
Last but not least, don't forget about FreeBSD (and NetBSD, and OpenBSD)!