I noticed that the staging environment had different content in its wp-config.php and .htaccess files. I changed them to be closer to the ones on the live environment.
While I was there, I noticed that some of the differing content was related to various caching plugins that we previously had installed on the staging environment. In desperation, I reinstalled all of those plugins through wp-admin and then uninstalled them.
Surprisingly, that fixed the issue of the cookies not being sent. However, the cookies had incorrect paths or domains. After some trial and error, I finally got it working by adding these seven lines to wp-config.php:
define('ADMIN_COOKIE_PATH', '/wp-admin');
define('COOKIE_DOMAIN', '');
define('COOKIEPATH', "https://wordpress.stackexchange.com/");
define('SITECOOKIEPATH', "https://wordpress.stackexchange.com/");
define('DOMAIN_CURRENT_SITE', 'test.example.com');
define('WP_HOME','https://test.example.com');
define('WP_SITEURL','https://test.example.com');
My assumption is that one or more of the caching plugins hadn’t cleaned up after itself when we uninstalled it.