I've figured this out myself... but I thought I might just let the list archives know so that others don't need to work it out for themselves.
To create a md5 password suitable for use in the PostgreSQL pg_shadow table:
$md5_passwd = 'md5' . md5( $password . $username );
The username acts as salt.