I don't understand how Faraday figured out that the emf induced when a magnet is moved in a coil would be equal to the rate of change of magnetic flux.
Faraday did many experiments of his own and considered the experiments of others and from that he produced a theory which in its modern form we call Faraday's Law.
Michael Faraday· Discovery of Electromagnetic Induction is a paper which gives you a detailed explanation of what Faraday did and here are a few extracts to give you a flavour of the events which produced the theory.
The discovery of electro-magnetic induction took place through a series of experiments that he conducted from August 29 to November 4, 1831.
Have an iron ring made, iron round and 7/8 inches thick and the ring 6 inches in external diameter. Wound many coils of copper wire round one half, the coils being separated by twine and calico. There were 3 lengths of wire each about 24 feet long and they could be connected as one length or used as separate lengths .... Will call this side of the ring A. On the other side but separated by an interval was wound wire in two pieces together amounting to about 60 feet in
length, the direction being as with the former coils; this side call B
Connected the ends of one of the pieces on A side with battery; immediately a sensible effect on the needle. It oscillated and settled at last in original position. On breaking connection of A side with battery again a disturbance of the needle ... Continued the contact of A side with battery but broke and closed alternately contact of B side. No effect at such times on the needle - depends upon the change in the battery side. Hence is no permanent or peculiar state of wire from B but effect due to a wave of electricity caused at moments of breaking and completing contacts at A side.
The [Mathematical] theory needed a new kind of concept, the question of the
electromagnetic field, and also the question of lines of force. Faraday introduced these concepts at various times between 1822 and 1836 but they remained unacceptable to the community of physicists during Faraday's time.
The first support of Faraday's field concept came from William
Thomson, later Lord Kelvin. Thomson showed that lines of
force could be used to explain the mathematical theory of
electrostatic action. This approach was brought to completion
by James Clark Maxwell in 1855. Maxwell used Faraday's
concepts about changing magnetic flux to lay the foundations of
a complete theory of electromagnetism.