How to auto send email when publishing a custom post type?

Hook into transition_post_status, fetch the users and send an email to all users.

Sample code, not tested:

add_action( 'transition_post_status', 'send_mails_on_publish', 10, 3 );

function send_mails_on_publish( $new_status, $old_status, $post )
{
    if ( 'publish' !== $new_status or 'publish' === $old_status
        or 'my_custom_type' !== get_post_type( $post ) )
        return;

    $subscribers = get_users( array ( 'role' => 'subscriber' ) );
    $emails      = array ();

    foreach ( $subscribers as $subscriber )
        $emails[] = $subscriber->user_email;

    $body = sprintf( 'Hey there is a new entry!
        See <%s>',
        get_permalink( $post )
    );


    wp_mail( $emails, 'New entry!', $body );
}

You should probably use the Bcc field.