The MQMD MessageId field is made up of both character and binary values.  Therefore, the only way to properly represent the MessageId field as a String is by converting it to HEX representation.
You need to use my bytesToHex method:
String s = bytesToHex(theMessage.messageId);
Hence, s would look something like '414D51204D5141312020202020202020134CCD4020000B01'.
And the Java code for bytesToHex method is:
public static final String HEX_CHARS = "0123456789ABCDEF";
public static String bytesToHex(byte[] data)
{
   StringBuffer buf = new StringBuffer();
   for (int i = 0; i < data.length; i++)
      buf.append(byteToHex(data[i]));
   return buf.toString();
}
public static String byteToHex(byte data)
{
   int hi = (data & 0xF0) >> 4;
   int lo = (data & 0x0F);
   return "" + HEX_CHARS.charAt(hi) + HEX_CHARS.charAt(lo);
}
Updated July 23, 2020.
Here is a method to convert a HEX string to a byte array:
public static byte[] hexStringToByteArray(String inString)
{
   byte[] outBuffer = new byte[inString.length()/2];
   String hex;
   int xx;
   for (int i=0, j=0; j < (inString.length() - 1); i++, j+=2)
   {
      hex = inString.substring(j,j+2);
      xx = Integer.parseInt(hex.trim(), 16);
      if (xx < 0)
         xx += 256;
      outBuffer[i] = (byte)xx;
   }
   return outBuffer;
}