The AM/PM curve of a power amplifier gives the difference in phase of the output and the input signal in dependence of the input power/ amplitude. Now, this phase difference is said to be 'normalized on the small-signal phase difference'. I am not sure what this means. 

My intuition: When I consider a signal with low amplitude and initial phase Theta_1 and let it be distorted by a PA, such that the phase of my output signal is given by Theta_2, the phase difference is just Theta_2-Theta_1. When I increase the amplitude of the input signal, I don't see why my initial phase would change. So.. I kind of don't get it.

For the increased input amplitude (input phase is still Theta_1), let us say you measure PA output phase as Theta_3. By "normalizing on the small-signal phase difference" it means you look at "Theta_3-Theta_2" only. 

In the AMAM,AMPM model it is only the normalized curve that matters since any constant output amplitude/phase change (w.r.t input amplitude) by the PA is a linear gain that needs to be same across different PA models for a fair comparison.

Hope this helps!

It means that the signal is small enough that the nonlinearity is negligible.  It's a measure of the dynamic characteristics of the amplifier (e.g. the linear differential equations part).  In other words, the frequency response and the phase response under those conditions.