All sotware should be distributed with a statement of what you are allowed to do with that software. Usually this is in the form of a license, e.g. GPL, BSD, MIT/X11. Without this statement the assumption is that you are not allowed to do anything with the software.
There are two issues with licenses and Debian packages. The first is freeness, the second is documentation.
Debian has the Debian Free Software Guidelines (DFSG). These state what it means for a software license to be "free". Only licenses that meet these requirements can be distributed in Debian. Some software that doesn't meet these criteria can be distributed in non-free.
As a packager you must decide whether the license that your package is under meets the requirements. If it is a common license then that is easy, as you can just look it up. If it is not then debian-legal can help you decide.
The second issue is that of documentation. Like Copyright all the licenses
of a package must be documented in the
debian/copyright file. To do this you
need to to through the package and inspect all the files to find all the licenses.
Most files will have a header describing the license, if they don't you can request
that the authors add them.
If you find files that are not under a DFSG-free license then see NonFreeFiles.
Some links that might be useful
- How (not) to write copyright files: http://lists.debian.org/debian-devel-announce/2006/03/msg00023.html
- DFSG status of common licenses: http://wiki.debian.org/DFSGLicenses
- debian-legal mailing list: http://lists.debian.org/debian-legal/