I've heard that inertial frames are frames in which Newton's laws hold.
The modern view of Newton's first law is that it defines the concept of an inertial frame. It also, at least conceptually, provides a mechanism for testing whether a frame of reference is an inertial frame. Suppose you know that no forces act on some particle. If that particle appears to be accelerating from your perspective, a reference frame that represents that perspective is not an inertial frame.
It's also important to look at Newton's first law from a historical context. Newton's first law was an extremely revolutionary statement. With that law, Newton was saying right up front that the Aristotelian physics that was still widely taught in Newton's time was fundamentally flawed.
Aristotelian physics taught that except for heavenly bodies, the natural state of some object was to come to rest. If you shoot at arrow in the air, it will eventually come to rest, embedded in the ground. If you roll a boulder down a hill, it will eventually come to rest, sitting still at the bottom of the hill. If you push a heavy object, it will move, but as soon as you stop pushing, it comes to rest. if If you throw a pebble in a pond, you'll make little waves in the pond, but eventually they too come to rest. Everything seemed to have a tendency to come to rest. That perceived natural tendency for objects to come to rest was what Newton was fighting with his first law.
How does it follow that the second and third laws also hold in that frame?
They doesn't follow, at least not logically. They are instead observational laws, the third law in particular. There are cases where Newton's third law fails. A force that arises from three (but not two) interacting bodies contradicts Newton's third law, and there are indeed three body quantum interactions that contradict Newton's third law. A force that involves some delay contradicts Newton's third law. Physicists in the latter part of the 19th century faced a serious conundrum in that Newton's mechanics and Maxwell's electrodynamics were in deep conflict with one another.
What about Newton's second law? There are (at least) a couple of different ways of looking at this. One is that Newton's second law is also definitional. It defines what "force" means. From this perspective, it's only Newton's third law that is a law of nature. This is the modern perspective of Newton's second law. It's the basis for why we write $F=ma$ as opposed to $F=kma$, where $k$ is some constant that relates force, mass, and acceleration.
In Newton's time, force was viewed as something distinct from the product of mass and acceleration. Newton devoted a good amount of space in his Principia to experiments from Galileo as tests of this law. This older point of view manifests itself in the customary units that are still used in the US. In the US, the pound is both a unit of mass and a unit of force. People in the US who use pounds mass and pounds force have to use that older style of Newton's second law, $F=kma$.
There are two ways to look at units that let us simply use $F=ma$ instead of the more verbose $F=kma$. One view is that this is merely a convenient trick. The conversion between force and mass*acceleration is still there, but subtlety hidden. The modern view is that using $F=ma$ represents something very fundamental, that force is the product of mass and acceleration. This is why the metric system's Newton is viewed as a derived unit rather than as a fundamental unit.
Wikipedia says that both newtonian mechanics and special relativity assume equivalence of inertial frames.
Acceleration is frame invariant in Newtonian mechanics. What that means is that the acceleration of a particle as observed in one inertial frame is exactly the same in all other inertial frames. It gets a bit trickier in special relativity. Removing the effects of time dilation and length contraction leads to the concept of proper acceleration, and this is frame invariant in special relativity.
