Should I just send an e-mail to the maintainer address listed in the module documentation

That's a good way to start, particularly if you're thinking about doing a good deal of work and if you might be annoyed if you did the work and found that it wasn't accepted. Also, some authors keep a source code repository and may be willing to give you access. Even if they don't, it might be helpful to know if they prefer to get patches against current code or a complete tarball of changes.

You can also submit patches via the RT bug tracker -- this makes your work visible to others, which is often handy for bug-fixes where the maintainer is slow to apply submitted patches.

As a minor note -- if you're working with someone's code, it's a good idea to try to match their style, space vs. tab preference and so on. If they use Perl::Tidy or Perl::Critic they may be able to share their settings with you.