Just a quick note about how MSMQ reports message size.

If you look in the Computer Management snap-in you will see a column marked "size". This is not the message size; it is instead the message BODY size. 

 

I have already populated the queue with 10 messages containing a 10-character payload in my example screenshot. As the 10 characters are in Unicode (double-byte), they take up 20 bytes instead of 10.

To get an idea of the actual message size, have a look in Performance Monitor:

 

As you can see, there are 10 messages taking up 2,440 bytes. So each message must be averaging 244 bytes - 20 bytes of which is the 10 character payload, 20-22 bytes for the label (again double-byte Unicode) and the rest is overhead.

To get an idea of what sort of things constitute this overhead you can look through the MSMQ API on MSDN or, more simply, have a look at what other column headings are available in Computer Management:

For example, I found after adding the various queue name lengths that both "recipient queue name length" and "destination queue format name length" were 44 bytes long (for the PUBLIC={GUID} queue name used by my application to send the messages).

If the actual message size is critical to your system then you could, if you really wanted to, track down and account for all the bytes in the message.

It is not possible to generalise about how big the overhead will be, though, without benchmarking it yourself with a wide range of representative messages.