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;

WRONG WAY:

message.setJMSPriority(priority); // THIS DOES NOT WORK!

sender.send(message);

CORRECT WAY:

sender.send(message, DeliveryMode.PERSISTENT, priority, 0);