In Australia, to progress from a Learner's license to a provisional driving license, you need to drive for 120 hours supervised by a person who has a full license. However, I know that it is illegal in Queensland to pay someone who isn't an instructor for those hours. Is this the same in New South Wales?
Yes, it’s illegal
The relevant law is the Driving Instructors Act 1992:
6 Unlicensed driving instruction
A person must not act as a driving instructor unless the person is the holder of a licence.
Maximum penalty—50 penalty units.
s7 makes it illegal for the person engaging the unlicensed instructor - with the same fine.
A person who is not paid or otherwise rewarded for the instruction is, by definition, not a driving instructor.