Ordering is done first on priority, then on message ID (which gets incremented per message sent). Assuming priorities for a set of messages is the same, and you are sending a message using a single thread/session, they will be returned in the same relative order when received by a single thread consumer. This is guaranteed ordering.
The priority of the message is either specified on the MessageProducer or as a parameter
to the send/publish operation.
It is a common mistake to try to set it on the message. This has no affect.
QueueSender sender = session.createSender(myQueue);
Message message = session.createTextMessage("hello");
int priority = 1;
message.setJMSPriority(priority); // THIS DOES NOT WORK!
sender.send(message, DeliveryMode.PERSISTENT, priority, 0);