When you edit media priorities in the Priority Editor, keyframes are not created by default. To create keyframes from the Priority Editor, the Auto Key button must be enabled. By default, the Auto Key button is set to off so as not to create keyframes when reordering media.
To create keyframes for a media priority change: