I found a line in the xbox support docs that is, at least for me, inaccurate. It says the xbox will check for updates in the "off" state (instant-on low power state), which happens every time I shut the xbox down at night. However, that's not working.
What I figured out after reading this, and some trial and error, was that I have my Xbox set to "never turn off automatically", and for some reason, this turns off the auto downloading. Despite the fact that the docs say it should work regardless of that particular setting's value, as long as you turn your console off once in a while (which I do), I wasn't seeing downloads come through.
But, after switching my console to turn off after 6 hours of inactivity, uninstalling an update, and turning the console off manually, I am now seeing the update download automatically in the "off" state, as well as in the background after starting the console.