I understand that Hooke's Law is $F=-kx$, and that this law only applies when a spring is not "overstreched." However, does Hooke's Law apply to all springs, or only simple harmonic oscillating springs?
To take it a step further, what is a simple harmonic oscillator defined as?
There are springs explicitly designed to deviate from Hooke's law in a repeatable and predictable manner.
In this example, this is done without using the possible intrinsic non-linearities of the material. The steel itself is used well inside its Hooke-abiding deformation range in order to be acceptably reliable.
So the short answer is No.
Like many empirical laws in Physics, Hooke's law only approximates the elastic bodies behavior.
In regard to the harmonic oscillator: this is an idealized model.
A simple spring with a massive object on one end and the other end held stationary behaves more or less as a harmonic oscillator if one is careful to excite it exactly longitudinally and not to excite it too much.
Hooke's law is valid for all springs when they are not "overstretched" (except possibly one designed specifically not to obey it, more on that in a bit). This also applies to other systems with a position-dependent restoring force (not just springs). However, such systems differ in how far you can stretch them before they begin to violate Hooke's law.
Suppose the spring force is some function $F(x)$, where $x=0$ is the equilibrium position, i.e. $F(0) = 0$. The Taylor expansion around $x=0$ gives $$ F(x) = F'(0)x + \frac{F''(0)}{2!}x^2+\frac{F'''(0)}{3!}x^3+\ldots$$ If $F'(0)$ is not zero (I know of no example where it is zero, but perhaps it's possible to design such a spring?), by definition, the spring constant is $k=-F'(0)$. Note that for small displacements, terms of order $>1$ will be much smaller that the "Hooke's law" term of order $1$, so the spring will obey Hooke's law.
You may then ask "for what range of displacements does the spring obey Hooke's law"? This will depend on the spring. If the second term is greater than terms of higher order when the spring becomes overstretched, the condition for the validity of Hooke's law is that the first term be much greater in magnitude than the second, which requires $$|x|\ll\frac{2k}{|F''(0)|}.$$
It may happen that $F''(0)$ is small enough that the linear range of the spring is determined by the third order term. To understand why, note that the second order term is either always positive or always negative, depending on the sign of $F''(0)$. This means that whichever way you extend the spring, the corresponding force is always in the same direction (not always toward the equilibrium position). Springs do not behave this way, so the second order term is often small compared to the third, or perhaps comparable.
In this case, Hooke's law's validity also requires that the third order term be much smaller in magnitude than the first, which is equivalent to the condition $$|x|\ll\sqrt{\frac{6k}{|F'''(0)|}}.$$
Hooke's law applies only to springy things where the deflection response is linear, as in the case for small deflections of elastic solids.
It does not apply for nonlinear springs like that represented by a piston in a cylinder full of gas or a length of rubber band.
A simple harmonic oscillator (SHM) can be defined as a second order dynamical system which contains energy storage elements whose constituitive relations are linear in the applicable flow and effort variables, and not functions of time, displacement, or velocity. The solution of the resulting differential equations of motion will then be a sine or cosine function versus time.
Hooke’s law for mechanical springs is the large-scale effect of the intermolecular forces in the material following an $F=-K_{m}x_m$ rule for small displacements between the molecules.
When you apply a force to one end of the spring, each pair of molecules displaces proportionally to this force, and the end of the spring moves by the sum of these displacements. (The full force at the end of the spring is applied to each cross-section of the spring —- forces are transmitted through the structure, not “absorbed” by intermediate pieces.)
(The above description is directly applicable to springs that are “sticks” being stretched or compressed along their lengths. For a coil spring, pulling on the ends of the spring causes all of the wire pieces to twist, which pushes and pulls molecules against each other. A few extra “lever arms” get involved in the calculations, related to the radius of the wire and the radius and pitch of the coil, but the overall idea is the same. For a leaf spring, the molecules are moved relative to each other when the spring bends.)
For springs in which the material has a “uniform” distribution (like a coil with constant radius and pitch), the internal deformation is evenly distributed, with the result that the displacement between any pair of molecules (and thus the force in the spring) is proportional to the total displacement of the end of the spring. This then becomes Hooke’s law for simple springs, $F=-K_{s}x$
It is possible to alter the geometry of the spring to get nonlinear springs. In @fraxinus’s answer, the progressive-rate spring has a coil that becomes “flatter” near the top. These parts twist more easily when force is applied at the end of the spring. On its own, this change in winding pitch just means that we need to take into account the different “lever arms” at different parts of the coil when calculating the total stiffness. Because they move more easily, however, the flatter coils will start to touch each other as the spring compresses; this “takes them out of play” by preventing them from compressing any more, so further displacement is distributed over a shorter section of the spring, so that the ratio between movement of the end of the the spring and the intermolecular displacements gets larger. This makes the spring force increase as faster than linearly as the spring is compressed. The exact rate at which the force goes up (i.e. the coefficients in the series that appear in other answers) depends on the winding pattern of the spring.
For the dual-rate spring in @fraxinus’s answer, the flat set of coils bottom out all at once, so that the total stiffness is the combination of the two stiffnesses (dominated by the softer of the two values) for small displacements, and then abruptly changes to the stiffer spring rate when the soft spring is fully compressed.
[“Combining” spring stiffnesses in series actually follows the rule $1/K = 1/K_1 + 1/K_2$, such that the combined spring stiffness is smaller than either of the individual springs, and is approximately the stiffness of the softer spring when the springs are of very different stiffness.]
It is also possible to make a “constant force” spring in which the spring force is independent of the extension of the spring. A common construction is a spool of metal tape that is heat treated after winding so that its resting configuration is the coiled shape. Putting this coil on a spindle and then pulling the free end away from the coil will result in most of the unspooled section being pulled straight, with a short curved region transitioning between the spooled and straight sections. Pulling on the end of the tape doesn’t bend the straight section, so the straight section is “out of play” like the bottomed out coils, with the result that the retraction force from the spring trying to spool itself back up is independent of how much material has been unspooled, and thus is independent of the displacement of the end of the spring.
(Many of these ideas, especially the structure of the constant-force spring can be expressed more rigorously if we start by saying that the spring rate is the derivative with respect to displacement of the energy stored in the system, but this appears to be a bit above the level at which the question was being asked.)
