Provide more help if the user doesn't have the permissions set

Can you think of any other modules which do this? The installation instructions that come with the module do include this instruction, so I'm hesitant to add it elsewhere unless that other place is a standard place to add it.

Setting up permissions for a module is standard procedure. You have to do the same thing for all core modules. Why should we make contrib modules do anything different? Also see http://drupal.org/getting-started/install-contrib/modules

The module admin page does tell you about settings on nodes if you haven't set those up properly, so I'm fine with making some messages here.

Maybe if none of the roles have the right permission we would set a message that says "You probably want some of your users to be able to use this dang thing! [link to permissions page]"

If anything I'd recommend a hook_requirements check. In D7 we have links to the permissions for the module on the admin/config/modules page to let you know which modules have permissions to assign.

hook_requirements is out of the context of the module, though. People go to admin/settings/comment_notify - we should give them all the information they need right there to configure it and do so in a way that once it's done they are no longer bothered by it (i.e. the green line in the report of hook_requirements "you configured permissions for module X" would get extreme really quickly).

I'm thinking more like how update.module does it and how I've implemented this in gravatar.module:

/**
 * Implementation of hook_help().
 */
function mymodule_help($path, $arg) {
  switch ($path) {
    case 'admin/settings/mymodule':
      module_load_install('mymodule');
      $requirements = mymodule_requirements('runtime');
      // If there are warning or error requirements and the user has the 'access site configuration' permission, do the following:
        drupal_set_message(t('One or more problems were detected with your [module name] configuration. Please check the <a href="@status-report">status report</a> for more information.', array('@status-report' => url('admin/reports/status'))), 'error', FALSE);
      break;
  }
}

Aha - ok. That makes a lot of sense. This makes more sense to put these kinds of things in a hook_help.