- Write manpages. Yes. Really. Write them. Well. It's basically: If your program/tool has a help and version commandline option you can simply run help2man and have a working start.
What may not be obvious to the recently REJECTed developer is actually how to use help2man. To try t0 explain the process a bit more verbosely, I took the liberty of writing a tutorial on the Debian wiki. Comments and corrections are welcome.
Of course, help2man-generated manpages are no substitute for real, hand-written manpages made of sweat, blood, and the Maintainer's tears, and it won't work for all packages. This is just a start, and is much better than no manpages at all.
There was a discussion on #debian-devel a couple of days ago when I brought up my creation of the above, and some wondered if it wouldn't be better to add hooks to man-db to allow package maintainers to enable manpage generation at runtime. I'm not sure if that idea will ever make it into a proposal, but, if the details of the implementation were worked out, would be much better than the above, manually generated method.