Einstein originally thought that special relativity was about light and how it always travelled at the same speed. Nowadays, we think that special relativity is about the idea that there is some universal speed limit on the transfer of information (and experiments tell us that photons, the quanta of light, move with the largest speed, $c$).
But what if tomorrow we happen to observe a particle $X$ that travels with a speed $v>c$? What changes would have to be made to special relativity?
If (and that's a big if) tomorrow we had a $70\sigma$ detection in a repeatable experiment of a particle that travelled faster than $c$, then one of several things would be true.
1) We would be forced to conclude that $c$ is not, in fact, the limiting speed of information transfer; everything based on this assumption would have to be scrapped (pretty much all of research-level physics); and we would have to start over in developing even the mathematics that allows us to start re-describing the universe.
2) We would be forced to conclude that $c$ is not the limiting speed of information transfer; we would assume that special relativity and everything based on it is the special-case effective theory of much broader physical laws and behaviours; and we would have to find a way of modifying relativity (and basically everything that relies on it) so that it can causally allow for this particle to exist and yet have everything else we see still basically operate under the idea that $c$ is the max speed.
3) We find a way to use this particle to communicate with the past and future, travel faster than light, and then we go home every night and laugh at Einstein.
4) We perform the experiment thousands of times in different laboratories, find the same result, then go back and discover that there was a fundamental flaw with the theory. Once the flaw is corrected, we see that we are not actually observing a superluminal particle.
5) We also discover flying pigs, perpetual motion, and that we really can believe it's not butter. Then I wake up from my nightmare.
My money is on (4) with (2) being a close second (although (5) has happened before).
Note: This answer assumes that the speed $c$ referenced is the assumed maximum speed; the speed of a massless particle in a vacuum. This is why I did not include a "we determine the photon is not massless and then have to change EM" option.
But what if tomorrow we happen to observe a particle X that travels with a speed V>c?
We would have made the first observation of a tachyon.
In special relativity, a faster-than-light particle would have space-like four-momentum, in contrast to ordinary particles that have time-like four-momentum. It would also have imaginary mass. Being constrained to the spacelike portion of the energy–momentum graph, it could not slow down to subluminal speeds.
I'd like to continue from Jims Bond's already comprehensive answer. Suppose that we had conclusive proof of our observation of a $V>c$ and that we've ruled out alternative (5) of Jim's answer. I agree with Jim that the next most likely of Jim's alternatives is:
2) We would be forced to conclude that $c$ is not the limiting speed of information transfer; we would assume that special relativity and everything based on it is the special-case effective theory of much broader physical laws and behaviours; and we would have to find a way of modifying relativity (and basically everything that relies on it) so that it can causally allow for this particle to exist and yet have everything else we see still basically operate under the idea that $c$ is the max speed.
Before we do this, the first question I would ask and the first test I'd be contemplating is how does our observed $V$ transform between different inertial observers? Perhaps the transformation law is tested and found to be as foreseen by the Lorentz transformation. It's perfectly possible and indeed I should think the most likely outcome. This means that some observers will see the particle travelling backwards. This would mean that the transformations and kinematics of special relativity could still work, presumably general relativity could still work (the equivalence principle would still meaningfully imply local Minkowskian neighborhoods of any spacetime event) but there would be at least three alternative consequences I can think of:
We basically have the tachyon observation as in Alfred's Answer. Moreover, there are now some causal relationships in our universe that point backwards in time. We'd have to explain how it is that most causal relationships in physics point forwards with effect coming after cause, but, for these particular particles, this can be reversed;
The observed propagation is real and with $V>c$, but the sequence of events that make up the "particle's" observed propagation are not causally related. I'm thinking here of a physical phenomenon that I call a "Mexican Wave by Prior Arrangement". An example of a phenomenon in this category is the sweeping a laser pointer across the surface of the Moon from Earth, such that the spot is seen to sweep at greater than $c$ (this happens if you sweep the laser pointer so that its angular velocity is greater than about 45 degrees per second). It's possible that our observed $V>c$ is a version of this. Here, the physical process involves a preprogramming phase, where neighboring processes happenning points in spacetime are preprogrammed to fire at "prearranged" times in the future, so that, when they do fire, the effect is that neighboring processes fire in quick succession such that the experimental effect is of a process propagating at faster than $c$. But the "preprogramming" part of the process happens subluminally, and therefore cause-effect relationships throughout the preprogramming always point forward for all observers, whereas the observed propagation can seem to propagate backwards in time.
Now we get to the nasty alternative: our particle's $V$ is observed to transform in a way that is different from the Lorentz transformation. Perhaps even this new speed $V$ is itself invariant! We know $c$ is invariant experimentally, and this sets the form of the Lorentz transformation given very basic assumptions like Galileo's Relativity Principle and Copernican notions of spatial isotropy and homogeneity. If the observed $V>c$ transforms in a way different from that foretold by the Lorentz transformation with invariant speed $c$, then this implies some of our very basic assumptions about the universe are wrong in some cases. Galileo's principle might be wrong. Homogeneity might be wrong, even on small scales. Isotropy might be flawed. One of these basic assumptions has to break.
The possible room for the nasty alternative scenario mentioned in WetSavannaAnimal's answer has been worked out in detail in this article. When the OPERA experiment due to a flawed cable connection appeared to have seen faster than light neutrinos, it was possible to calculate that this was impossible, because the room there exists for Lorentz invariance violations would predict that the neutrinos would have emitted vacuum Cherenkov radiation and as a result the energy spectrum would have had to be affected in a way that was not seen, see here.
