The encryption would use IPSec, IPSec exists below the Transport layer so its encryption services are transparent to applications. This means you don't need to change how the MSMQ application works - if it can send messages successfully over the unsecured network it should perform as well when IPSEC has been enabled.
There should be no issues in configuring this way, however this configuration has not been tested with our application. As such we are unable to commit as to whether it is supported.
The section ?Configuration for Batch Processing? in chapter 5 of the current System Reference (available through the title page of online help in any implementation) may help. There is also a diagram to display the flow of data between each section of the system.
Please ensure that in a multi-server implementation, the same service account must be used on all central servers. This is required for proper functioning of Microsoft Message Queueing between the servers.