I think he deduced it as a consequence of Maxwell's equations. That's where he got the symbol "c" from, I'm told. But as always, I'll yield to the experts, who often correct my babblings.
While you can deduce the speed of light from Maxwell's equations, it's something of a trick, and doesn't get into the notion that it must be the same for all observers regardless of relative motion. Eisten started with the speed of light being constant for all observers, and deduced that is was also the maxium possible speed, and that E=mc2. The observations that suggested this assumption were the Michelson-Morely eperiments that attempted to deduce the "true" motion of the earth through the "ether" by measuring differences in the speed of light in different directions. No difference was found.