Where is the User’s Admin Bar Preference stored? I want it to default to off for new users

You can update the usermeta upon user registration.

Try adding this to functions.php and then adding a new user:

add_action('user_register', 'update_usermeta_bar', 10, 1);

function update_usermeta_bar($user_id)
{

    update_user_meta($user_id, 'show_admin_bar_front', "false");
}