How common is it to inadvertently publish a finding that was already discovered?
Far more common than anyone realizes or wants to admit.
Stigler's Law of Eponymy states that No scientific discovery is named after its original discoverer. (Stigler's law was proposed in this precise form in 1980 by Stephen Stigler, who self-referentially attributed it to Richard Merton, but of course similar statements were made earlier by many others, including Stigler's own father.) I wouldn't go as far as claiming that every scientific discovery is misattributed, but there are hundreds of examples. Off the top of my head: Fibonacci numbers, Pascal's triangle, Gaussian elimination, Euler's formula (both of them!), Voronoi diagrams, Markov's inequality, Chebyshev’s inequality, Dijkstra's algorithm for shortest paths, Prim's algorithm for minimum spanning trees, the Cooley-Tukey FFT algorithm, the Gale-Shapley stable matching algorithm (for which Shapley recently won the Nobel Prize in economics), ...
What do you when you happen to find yourself in this situation?
Be brutally honest, both with yourself and with the scientific community.
If your work has already been published, post a reference to the prior art in your web page listing your publications. (You do have a web page listing your publications, don't you?) If possible, publish an addendum to your paper. Email anyone who has cited your paper already, giving them the earlier reference. When asked to review papers that cite your paper, include the earlier reference in your report. Become a walking advertisement for the earlier work.
If your work hasn't already been published, try to figure out which parts of your work have actually been done before. Some of your results will appear verbatim in the earlier work, so you can't take credit for them. Some of your results will be easy corollaries of the earlier work, so you still can't take credit for them. But perhaps some of your results will take the old work in a new nontrivial direction. Build on that.
Also, if your results were previously known in a different field, there may be some value in bringing those results to the attention of your research community.
Should you just scrap your work if your methods are too similar to someone else's?
Of course not! Now you have evidence that your methods actually work! Push them further!