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
Clean_Sales_Block_Adminhtml_Sales_Order_Create_Form_Account::_prepareForm()
and
Clean_Sales_Model_Adminhtml_Sales_Order_Create::_prepareCustomer()
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.