Is it possible to quantify the work required to introduce order? Is there a thermodynamic analysis that allows us to say "in order to introduce this much order into this subsystem, this much work must have been done on it by the rest of the system"?
I assume that whatever is calculated here would be a lower bound, since the process could be made arbitrarily inefficient.
I also assume that the "order" here would be expressed in terms of a reduction in entropy of the subsystem, but it's not clear to me that that is a valid concept and I worry that I am conflating thermodynamic and information-theoretic concepts of entropy.
I am aware of Landauer's principle which seems closely related but not quite what I'm looking for.
My understanding of thermodynamics is pretty limited and I would appreciate pointers to foundational texts that would allow me to reason this out for myself.
 A: The relationship between thermodynamic and information entropy is still a work in progress. However, it is clear that he thermodynamic entropy is a rough measure of disorder,  in the sense of not knowing in which specific microstate, all compatible with a given macrostate, the system is. Thus there is at least a loose relationship between thermodynamic entropy an information. 
More specific to your question, a reduction in entropy in a subsystem can be reached in different ways, the basic relationship being: 
$dU = T dS - P dV$, 
Thus you can reduce entropy by doing negative work on the rest of the system, or by changing the internal energy by some other means (such as extracting heat, by putting the subsystem in contact to a lower temperature heat reservoir). 
For instance, if you want to reduce entropy by doing work and releasing heat such that the internal energy $U$ remains a constant,  you can set $dU=0$, and compress the subsystem. To make a concrete example assume the subsystem is an ideal gas, so $PV=nRT$, then you get:
$dS=nR\frac{dV}{V}$
which gives the change (reduction) in entropy for a non-adiabatic compression.
