I'm still assuming there's probably a native way to do this in Magento but haven't found it yet.
The way I ended up solving it was by rewriting
Both of the rewrites can be done pretty cleanly by relying on the parent method and then just dropping in the logic after that.
At first I thought I could get away with using a Customer Attribute (if you're on Enterprise) called
is_subscribed, but it's not a very clean solution. It will subscribe the customer but it won't respect the newsletter subscriber's state for subsequent orders and generally won't be sync'd with the subscriber status.