You could use timestamp Longs as keys in the Node and sort the results of a Node.getData() call.
Well, the millisecond precision is probably not good enough, and if several machines are involved then it would require very precise time synchronization.
On the other hand, if the queue is kept in a node, then won't every add/remove operation lock the whole node (thus the whole queue)?
Java 5's System.nanoTime(), perhaps?
Clock syncing to that level of precision may become a problem in a large cluster though.
Isn't it a good thing that the queue is locked for add/remove operations?
although with a high degree of writes I think what you really need is a JMS queue.