> - what would be the API of this atfork() mechanism (with an example of how it would be used in the library)?

The atfork API is defined in POSIX and Gregory P. Smith proposed a Python one above that we can look into.
http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_atfork.html

We may need an API to reset a lock.

> - how do you find the correct order to acquire locks in the parent process?

One option is to use the import graph to determine call order of atfork handlers. 
If a current std library does not fit into this scheme we can possibly fix it when writing its handlers.

> - what do you do with locks that can be held for arbitrarily long (e.g. I/O locks)?

It is likely that such a lock does not need acquiring at the parent, and re-initializing the library in the child handler will do.
A  "critical section" lock that protects in-memory data should not be held for long.