There's an immense amount of variation over what goes into the package documentation for a module. Here's what I think should be in each file:
Your README file should tell me what the module is. It functions as an abstract: an abbreviated description of the module, a few paragraphs long. Most importantly, the README should tell me why I might want to use your module. I'm reading these via search.cpan.org's recent page, here, so don't assume I found your module because I was looking specifically for it. In particular, if your module is an interface to the JabXL C library, include a sentence or two telling me what the JabXL C library is for and pointing me to its homepage (or whatever).
The README should not include your module's documentation. That's what the embedded POD is for. The README should not include installation instructions. That's what the INSTALL file is for.
Your README should definitely not consist solely of module installation instructions.
Here I should find documentation for the public interface (API) to your module. This is "how to use it" for a programmer. Use POD. Check it with pod2man and perldoc, one or both of which will bark at you to remind you of what sections you need.
Installation instructions don't belong here, either, especially not at the top. I may read this once before installing, but I will read it hundreds of times after installing.
This might be every single little commit, or it might be a list of major changes for each version. I prefer the latter. Whichever you choose, you should put new entries at the top, so that the older versions are way down at the bottom of the file. It will make it easier on you and on me.
The GNU project calls this file ChangeLog.
The third-edition camel provides a much better introduction to installing modules than ever before. Module installation used to be sort of a black art from a newbie's point of view. It ought to be almost the same for every single module, but module authors of yore used to have to document the whole process or face answering "How do I install? What if I'm not root?" all the time. (And they had to document how to install for Macintosh, and every other little variation.) Many of us slowly learned the ins and outs of module installation by reading the documentation of several modules over a period of months or years, while today's newbies (lucky young whippersnappers) can learn what they need to know all in one place from the camel or the perlmodinstall page. And learn how to put it in their $HOME's, to boot.
Installation instructions don't belong in the README or the POD, but if you cannot suppress the urge, please put them at the bottom so I don't see them. A simple note at the top explaining that the installation instructions are at the bottom is acceptable. Those files should definitely have something else in them, too.
The GNU autotools produce a generic INSTALL file that works for most
Oft forgotten, the license files can be important in several ways. Please explicitly state what terms your module is available under, to satisfy corporate lawyers in other people's organizations so they can use your code.
In general, your module will probably be "free software" available under "the same terms as Perl itself," which means people can redistribute your module under the terms of either the Perl Artistic license or the GNU General Public License. If you want your module made available under different terms (just one of the two, or a different license entirely), stating your terms becomes even more important.
Assuming you choose the normal terms, please include the complete text of both licenses. New users (and the lawyers that obstruct them from doing their jobs) may not be familiar with the concept yet. In addition to reassuring them that it is okay for them to use your module in any way they want, this is a great opportunity to introduce them to the world of open source. The Perl Artistic license was the first open source license I ever read, and I remember thinking, "Wow! If I ever write anything worthwhile, that would be the way to release it! Shareware's such a waste, but this means other people can really do whatever they want with the program!"
The GNU project recommends you put a copyright and license notice at the top of every source code file, and include the GPL text, traditionally in a file named COPYING. The Artistic license is traditionally in a file named Artistic. I would put this notice in a comment at the top of each file of code: "This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself." You should make reference to the COPYING and Artistic files somewhere, preferably at the end of the module POD documentation.
You should have tests. They should pass.
Your Makefile.PL shouldn't ask any questions. It should determine things either on its own or by taking input on the command line. I want to run
perl5.6.1 Makefile.PL && make && make test && make install on one line, go off somewhere for ten minutes, come back, and then play with your module. I don't want to come back to find that nothing happened because the module is prompting me to enter a configuration option. Consider also what will happen when a user tries to install with CPAN.pm and cannot provide this input. Configuring your module may be so complex a task that it cannot be installed with CPAN.pm, but please don't make it so unless it has to be.
In general, think about when each file will be read and by whom. There shouldn't be a whole lot of overlap between each of the items I listed, with the possible exception of brief pointers to the appropriate location.
Please help save the world! Please encourage me to use your module when I see it on search.cpan.org/recent!