It seems that if you need another module in a function of your extension module, the way modules in the standard library seem to solve this is like this:

static PyObject *
func(void)
{
    PyObject *foo;

    foo = PyImport_ImportModuleNoBlock("foo");
    if (foo == NULL)
        return NULL;
    /* do stuff with foo */
    Py_DECREF(foo);
    return something;
}

This means that you have to import the module each time you enter the function (yes, it's looked up in the modules dict by PyImport_ImportModuleNoBlock() but that function is only avaliable since 2.6, before you have to use PyImport_ImportModule()).

Personally I like storing the module in a static variable so that it only needs to be imported the first time:

static PyObject *
func(void)
{
    static PyObject *foo = NULL;

    if (foo == NULL) {
        foo = PyImport_ImportModuleNoBlock("foo");
        if (foo == NULL)
            return NULL;
    }
    /* do stuff with foo */
    return something;
}

Note here that the Py_DECREF() is gone. This function will effectively leak a reference to the module object. But is this really bad? How often do module objects get deleted in production code? My guess is that they normally stay loaded until the application exits.