This is accomplished by _wp_auto_add_pages_to_menu() (in \wp-includes\nav-menu.php) function that is hooked to transition_post_status hook.
Unfortunately it is hardcoded for page post type and is not easy to extend.
On other hand since it works through generic hook it isn’t hard (relatively, menus internal code is pain) to engineer analogue for custom post type.