Most planets were found by someone looking. Neptune was found by someone calculating, and then by someone else looking where the calculation said to. That sequence has made it a standard example of Newtonian physics making a prediction that came true. The full story is messier and more useful than that, because the method's next big attempt went wrong.
A planet that wouldn't stay on schedule
William Herschel discovered Uranus in 1781. In 1821 the French astronomer Alexis Bouvard published tables predicting its position, built on Newton's law of gravitation and the pulls of the known planets. Uranus soon drifted away from them. The drift was small, but it was real, and it kept growing.
There were a few ways to explain it. The old observations could be wrong. Newton's law might not hold at such great distances from the Sun. Or something unseen beyond Uranus was pulling on it. The last idea led to an unusually hard problem. Normally you know a planet and work out how it disturbs its neighbours. Here the disturbance was known, and the planet causing it had to be worked out from it: its mass, its orbit, and where it was in the sky.
Two people working the problem
In Paris, Urbain Le Verrier took it up in a series of memoirs. On 10 November 1845 he showed that the existing theory couldn't account for Uranus's motion. On 1 June 1846 he gave a predicted position for the unknown planet. On 31 August he added its mass and orbit. French astronomers were slow to search, so he wrote to Johann Gottfried Galle at the Berlin Observatory.
Galle got the letter on the morning of 23 September 1846. The observatory's director, Johann Encke, let him use the 9-inch Fraunhofer refractor that night. A student, Heinrich d'Arrest, suggested comparing the sky against a newly printed star chart of that region instead of hunting for a visible disc. Soon after midnight, d'Arrest noticed a star that wasn't on the chart. It was less than a degree from Le Verrier's predicted position, and the search had taken less than an hour. Over the next two nights its motion against the stars confirmed it was a planet.
In Cambridge, a young mathematician named John Couch Adams had been working on the same problem since about 1843. When he first passed his results to anyone, and how clearly, has been argued over for a long time. The earliest written evidence for a September 1845 communication is a note that may have been dated afterward. James Challis at the Cambridge Observatory began a search on 29 July 1846, guided by Adams's figures. He actually recorded Neptune on 8 and 12 August. He didn't recognise it, because he was cataloguing every star in a large area and had no up-to-date map to compare against.
After Galle's announcement, George Airy, the Astronomer Royal, publicly put Adams forward as a co-discoverer. The resulting dispute between England and France was bitter. The Royal Society gave Le Verrier its Copley Medal in 1846 and Adams the same medal in 1848. For much of the following century, the usual English-language account gave the two men roughly equal credit.
That account has weakened. Adams's correspondence with Airy, long missing, turned up in 1999 among the papers of the astronomer Olin Eggen in Chile. Historians who studied it, including Nicholas Kollerstrom, found that Adams's predicted positions had wandered over roughly 20 degrees of sky across his several solutions. His last prediction, in early September 1846, was about 12 degrees off. In a 2004 Scientific American article, William Sheehan, Kollerstrom and Craig Waff concluded: "The achievement was Le Verrier's alone." Not every historian goes that far. But the case for equal credit now rests mostly on Adams starting first, not on his results being as good.
Right direction, wrong distance
One detail undercuts the triumphant version. Neither man knew how far away the planet was, so both took a starting distance from the Titius–Bode rule. That was a numerical pattern, not a physical law, that fit the planets out to Uranus fairly well. It put the next planet around 38 or 39 astronomical units from the Sun. Neptune's actual average distance is about 30. Their orbits were too large and their periods too long. In 1846 their predictions happened to agree with the real planet across the stretch of orbit that mattered, so the position on the sky came out nearly right. The astronomer André Danjon argued in 1946 that over that stretch the predicted orbits really were close to Neptune's, which is why the wrong distance did less damage than you might expect. Still, the method didn't recover the real orbit. Neptune also put an end to the Bode rule, which it doesn't fit.
Galileo had seen Neptune too. His notebooks record it on 28 December 1612 and 27 January 1613, near Jupiter, drawn as a star. A note suggests he noticed it had shifted, but he never followed up.
The same idea, pointed the other way
After Neptune, Le Verrier turned to Mercury. In 1859 he showed that the point of Mercury's closest approach to the Sun, its perihelion, was advancing a little faster than the known planets could explain. His figure was about 38 arcseconds per century. Later work by Simon Newcomb and others refined it to about 43. The reasoning that had worked for Uranus suggested an answer: an unseen planet, or a belt of small bodies, orbiting inside Mercury.
It looked confirmed almost at once. A French country doctor, Edmond Lescarbault, reported seeing a small dark spot cross the Sun on 26 March 1859. Le Verrier visited him, was convinced, and on 2 January 1860 announced the planet to the Académie des Sciences under the name Vulcan. Other observers, including Emmanuel Liais, said they had been watching the Sun at the same time and seen nothing. Reported sightings came and went for decades, mostly during solar eclipses, and none held up.
The actual explanation was found in 1915, long after Le Verrier's death in 1877. In Einstein's general relativity, gravity near a mass as large as the Sun behaves slightly differently from Newton's description. The correction predicts an extra perihelion advance for Mercury of about 43 arcseconds per century, with no hidden planet needed. It was one of the first observed results the new theory explained.
What I find most instructive is that the two cases weren't different in method. In both, a careful analyst saw a planet's orbit fail to match the theory and assumed the theory was right and something was missing. With Uranus, something was missing. With Mercury, the theory itself was the problem. Nothing in the residuals said which situation you were in. The only way to find out was to look. When people looked for Neptune it was there, and when they looked for Vulcan it wasn't.