Maya will import plugin files that are set to auto-load very early in its startup routine, much earlier than any user-specified startup scripts. Earlier, even, than PyMEL. This means that the initialization of your plugin must not use (or even import) PyMEL if it is set to auto-load.

For example, I've included part of the deferpymel.py plugin in the following code. The rest of the code can be found with the book's examples. Notice the import pymel.core line at the top of the file.

from maya import OpenMayaMPx
import pymel.core

# ... Other code here ...

def initializePlugin(mobject):
    plugin = _toplugin(mobject)
    plugin.registerCommand(plugin_name, create_plugin)

If we start Maya, set this plugin to auto-load, and restart Maya, we should see the following in the Script Editor after Maya starts up:

# // pymel.core : Updating pymel with pre-loaded plugins: deferpymel

PyMEL was loaded but it is in an incomplete state. On import, PyMEL dynamically...