Priority stack in Java
You can consider implementing the Deque interface so that you can potentially open up its usage as an implementation of the Collections classes. 

Your field size seems to be underused here, as I can sort of see a size() method using it too... BTW, regardless whether you use the Deque interface, your method empty() should be written as isEmpty(), to follow Java methods' naming convention as 'is...' for boolean return values.

Back to talking about Collections classes, they throw NoSuchElementException when no element can be returned, e.g. when empty, so perhaps you can throw that too instead of EmptyStackException.

Since you are relying on your TreeMap inner implementation, you can consider having your field declaration as TreeMap too instead of Map, this being one of those cases where using the implementation (class) rather than the interface makes more sense. With a TreeMap, you can replace map.entrySet().iterator().next().getValue() with the neater method map.firstEntry(). 

In your push() method, if you are on Java 8, you can consider computeIfAbsent():

public void push(E element, P priority) {
    map.computeIfAbsent(priority, ArrayList::new).add(element);
    size++;
}


Last but not least, you should have better unit testing too... Your current case looks OK already, so it's just a matter of comparing the output when you pop() to something you can compare with, such as a List. Remember to test for edge cases, such as getting from an empty instance, or adding null elements (which should be allowed given your ArrayList implementation).