For those interested, it turned out that there was no good solution to this. Even hand-building queries via HQL was extremely painful, since in order to reconstitute the list of returned objects I had to enumerate all of the attributes of the object and its ancestors in the select statement. And then even that broke, since it didn't properly order "Users" without any "messages".
I wound up just adding a derived property (e.g. "msgCount") to the object definition that represented the thing that I wanted to order by, and inserted a formula that consisted of a blob of SQL that calculated the property, e.g.
Code:
<joined-subclass name="com.example.User" table="user">
<property name="msgCount" lazy="true" formula="COALESCE((SELECT COUNT(msg.user_id) FROM Message msg WHERE msg.user_id = id GROUP BY msg.user_id), 0)"/>
</joined-subclass>
The "msgCount" property can then be referenced like any other property in the Criteria API. This is probably not the most efficient solution, but it seems to work.