What is the protocol for adding a new module dependency to a module that has only had a dev release?
There's no sanctioned protocol for such a case. All I think of is to minimize the impact.

Consider that even if you create a new branch, users may update and neither realize there's a new dependency, and your module may end up silently disabled because of unmet dependencies. This happened to the update of views from 6.x-2.x to 6.x-3.x where a dependency on ctools was added. In that case, the impact was low because ctools usually is present.

On documentation, in addition to changelog or upgrade doc in the project page, I suggest to add it to the release notes. Since they can be read easily when updating with drush.

Last, if the dependency you're introducing is a popular module, you can alleviate the impact by enabling the new dependency in hook_update_N or raising an error if not available. Here's some untested code:

&lt;?php
function MODULENAME_update_7001() {
  $enabled = module_enable(array('foo', 'bar'));
  if (!$enabled) {
    throw new DrupalUpdateException('foo required.');
  }
}