Newtonian mechanics was not yet in place when Hooke published his De Potentia Restitutiva (On Restoring Force) in 1678, Newton's Principia only came out in 1687. Hooke inferred the law from experiments not only with springs but also with wood and a "body of air", concluding:
"The power of any spring is in the same proportion with the tension thereof: that is, if one power stretch or bend it one space, two will bend it two, and three will bend it three, and so forward. Now as the theory is very short, so the way of trying it is very easie… it is very evident that… in every springing body… the force or power thereof to restore itself to its natural position is always proportionate to the distance or space it is removed therefrom".
This being said, Hooke did attempt a theoretical justification by imagining a mechanical model of springs as composed of tiny particles vibrating around some fixed positions, colliding with their neighbors and surrounded by "subtle matter". When the body is compressed the rate of collisions increases, accounting for the restoring force. When the body is stretched the force is provided by the pressure from "subtle matter". Although Hooke claims that the model leads to his law, modern analysis of his reasoning shows that it produces inverse square rather than proportional relationship. Today Hooke's law can be derived from more fundamental principles, but that requires assumptions about the molecular composition of matter and the nature of intermolecular forces, in addition to Newton's fundamental laws.
See Moyer's Robert Hooke's Ambiguous Presentation of "Hooke's Law".