MSMQ has moved out of private corporate LANs and now companies send messages over the Internet. Data security should therefore be top of the to-do list for anyone wanting to follow this route.

The first consideration is what do you actually need to encrypt? Are you only interested in ensuring that the message payload cannot be sniffed on the wire or must the content also be secure while in storage in the server's queues? This is important as MSMQ only natively provides the former.

Over-the-wire encryption

Using SSL
With MSMQ 3.0 and above came the ability to send messages using HTTP and HTTPS protocols. If you have an existing application then it will need to be changed so that the message addresses confirm to the different format (For example, DIRECT=HTTPS://URL_Address/msmq/PublicQueueName instead of DIRECT=ComputerAddress\PublicQueueName). 

The following are good reference material for configuring the application and webserver:

How to use Message Queuing 3.0 to perform secure Internet messaging over HTTPS in IIS

Configuring HTTPS Messaging for MSMQ 3.0

Using IPSEC

IPSec exists below the Transport layer so its encryption services are transparent to applications. This means you don't need to change how your MSMQ application works - if it can send messages successfully over the unsecured network it should perform as well when IPSEC has been enabled.

Here's the link to the TechNet resource for all things IPsec

Using MSMQ encryption

MSMQ has the functionality built-in to perform encryption using keys stored in directory services. Important note here - this means only domain members can send encrypted messages to each other. Cross-forest or workgroup-mode communication will not be able to take advantage of this feature.

The privacy level for the queue determines whether it accepts messages that are encrypted ("Body"), unencrypted ("None") or both ("Optional").

Setting this level, though, is only half the story as the application needs to ensure that messages are sent encrypted. Any unencrypted messages that arrive at a queue with body-level privacy will simply be discarded.

From the Motley Queüe blog:

"Let’s look first at what MSMQ encryption actually does. MSMQ messages can be encrypted by setting the Message.UseEncryption property if using System.Messaging, or PROPID_M_PRIV_LEVEL message property if using the native API.  When this property is set, the message body is encrypted using a key from the directory service when it is removed from the outgoing queue to be transmitted on the network.  At the destination machine, the message is decrypted and placed in the destination queue.  This type of encryption is a part of transport security — if the message were to be intercepted in transport, the contents would be safe."

Further reference material is here:

Message Encryption

MSMQ overhead when you use message security features

 

Using Application Encryption on the Message

To manually encrypt messages when there is no access to the directory service, you can choose to have the application encrypt the message body. 

From the MSDN article on Application-Encrypted Messages:

To encrypt a message body, the sending application must have an RC2 or RC4 symmetric key to encrypt the message body, as well as the public key of the receiving computer to encrypt the symmetric key. On the receiving side, the destination queue manager can decrypt the message only if the receiving computer is operating in domain mode.

 

Using Application Encryption on the Data

All of the above focus on protecting messages while they are on the wire. If you wish to ensure that the data carried by the message is secure end-to-end - even in the outgoing and destination queues - then you need to encrypt the data BEFORE giving it to MSMQ. An MSMQ message can carry any type of data so the fact that the information is an encrypted block of bytes won't matter - the queue manager will treat the message body just like any other unencrypted message.

This means that responsibility for encryption and key exchange lie fully with the application and its developer, not MSMQ. How to do that is a vast subject area in its own right and I'll leave that to the experts.