Checking packages
lintian and linda
TODO
piuparts
TODO
autopkgtests
TODO
edos-debcheck
TODO
yaclc
TODO
debi
Of course, you should actually install your new package as one part of checking it. “debi” saves some typing by installing the most recent .deb file found in a parent of the current directory. It requires root privileges, so you will actually type sudo debi (or, using bash's command history, perhaps just ^Rsu).
Debian Quality Assurance Site
If there is already a version of the package in the collection, you should review its entry at the QA site. You can start at http://packages.qa.debian.org/common/index.html. Check the “Bug Count”, “TODO”, and “Testing Status” sections.