The first hints of the existence of dark matter go all the way back to the 1930s. In 1932, it was noted that stars in the Milky Way were moving much faster than they should be; in fact, fast enough to actually escape the galaxy. But they couldn't be escaping the galaxy, or they'd have been gone long before now, as the galaxy is some 10 billion years old.
Later observations beginning in the 1950s showed that, rather than slowing down with distance from the center, the velocities of stars in their orbits around the center of many galaxies stayed the same. The planets of our solar system, by contrast, revolve around the Sun more and more slowly with increasing distance from the Sun. While Earth takes one year (by definition) to travel around the Sun, Pluto takes 248 years to make one such revolution. This translates into orbital speeds of about 30 km/sec for Earth and 4.7 km/sec for Pluto, and is referred to as "Keplerian" motion, after Johannes Kepler, who first correctly described the orbits of the planets.
It was expected that galaxies would rotate similarly; stars farther away from the center of the galaxy would be moving more slowly than stars nearer to the center. So the observation that, instead, the orbital speed of stars remained the same with increasing distance from the center was a remarkable result; it would be the same as if Pluto was found to be orbiting the Sun at 30 km/sec, the same speed as the Earth, and would mean that Pluto should fly off into space rather than remain in solar orbit.
In 1933, Fritz Zwicky pointed out a similar problem: the velocities of galaxies in galaxy clusters were too large for the clusters to be held together by gravitational attraction, unless there was far more mass in the galaxies than could be accounted for by the visible stars and gas. This was true even after accounting for the contributions of nonluminous gas and dust contained within the galaxies. What this meant is that the observed clusters of galaxies should have long since broken up; the galaxies should have dispersed long before now.
All of these problems could be solved in a similar way, by postulating that galaxies contained far more matter than could be accounted for by adding up all of the stars, gas, and dust. In fact, roughly the same amount of such additional matter solved both problems. Because this matter was non-luminous (else we could see it), the term "dark matter" was coined. The amount of this extra matter was not insignificant -- it was 5 to 10 times the amount of visible matter seen in the galaxies.
Let me pause here to point out that there is an alternative explanation; it could simply be that gravity is much stronger than we think it is over very large distances. There are several theories proposing this, but they've all encountered problems in the area of reconciling their predictions with observation. That is not, however, to say that all of them have been conclusively ruled out.
This immediately posed the problem of just what the dark matter could be. It cannot be invisible gas, rocks, or planets, because those would have infrared signatures which we do not see (remember, there's lots of this stuff). In addition, that much extra matter in the form of ordinary gas would block far too much light from the stars for it to actually exist -- so, whatever it was, it had to be transparent to light. Searches for even larger dark objects in the haloes of galaxies revealed nothing that could account for the huge amounts of extra mass required.
Further evidence in the hunt for dark matter emerged in the 1970s, when the process of production of the constituents of atoms in the early minutes of the Big Bang began to be well understood (to the point where it now predicts the correct abundances of hydrogen, helium, and lithium -- essentially the only elements produced by the Big Bang -- in the Universe). The total mass of elementary particles that could be produced during this phase seemed to be far smaller than the actual mass of the Universe based on observations and calculations of its expansion rate. This led to the suspicion that the Universe was filled with some unknown type of non-ordinary matter.
Then, in the 1990s, a map of temperature fluctuations in the very early Universe was made by NASA's COBE satellite, which measured, in every direction, the temperature of microwaves originating from light that were emitted as the Universe cooled about 380,000 years after the Big Bang. The fluctuations were remarkably tiny -- about one part in 100,000. This meant that the distribution of matter in the Universe at that time was much too smooth to have allowed gravity to make stars and galaxies in just a few hundred million years. Despite this, other observations indicated that there definitely were stars and primitive galaxies much sooner than one billion years after the Big Bang.
The solution to this problem was, once again, more matter, which would create more gravity. And this time it also had to be non-ordinary matter that interacted with ordinary matter through gravity alone. Studies of the detailed properties of the temperature fluctuations also yielded evidence of just how much of this non-ordinary matter there must be.
Through the latter half of the 20th century, telescopes and imaging techniques had become good enough, especially with the launch of space-based telescopes, that we began to get good imagery of the phenomenon of gravitational lensing. In 1915, Albert Einstein's general theory of relativity had predicted that gravity would bend the path of a beam of light, something not previously suspected, and observations of the solar eclipse of 1919 confirmed this.
The implication was that large concentrations of mass could bend light significantly -- enough to produce distorted and magnified images of background objects that lay behind the mass concentration (in a manner not too much different than a camera lens uses glass to bend light to produce images). High-resolution images of clusters of galaxies demonstrated just such an effect: distorted (and even multiple) images of galaxies that lay well beyond the lensing cluster could be seen. The distortion of these images has been used to calculate what the distribution of matter within those clusters must be in order to yield that distortion, and it turns out that these clusters seem to contain huge amounts of unseen matter distributed in a manner that is unrelated to the distribution of the galaxies that made up the cluster (in other words, there is a great deal of gravity between the galaxies, not just inside them).
This is one of the observations that causes difficulty for theories that claim gravity is stronger than we think; it's one thing to have a theory of gravity that produces more gravity inside a galaxy full of stars, but quite another to have a theory of gravity that produces lots of gravity in the empty space between galaxies, where there is essentially no mass at all.
So, at the present time, we're left with four observations which indicate that there is far more matter than we can see in the Universe:
All four of these observational difficulties can be resolved by adding roughly the same amount of dark matter to the Universe. Additionally, Big Bang nucleosynthesis and studies of the cosmic microwave background indicate that there is a great deal of non-ordinary (astronomers and physicsts call it "non-baryonic") nonluminous matter in the Universe.
As mentioned, another way to account for some of these observations is to modify the theory of gravity -- perhaps general relativity is not entirely correct. So far, however, such attempts only really solve problem number 1 and perhaps problem number 2. And, one by one, these modified gravity theories are failing other sensitive observational tests. Problem 4 is particularly difficult for such theories, because just making galaxies heavier through some modification of gravity does not correspond to the distribution of gravity as mapped by gravitational lensing.
And, finally, there is Occam's Razor, the precept that the simplest explanation is most likely to be correct. One idea, that of dark matter, solves all four problems while neatly accommodating the indications that there is a great deal of non-ordinary matter in the Universe. The alternative, at the moment, is that several separate new ideas would be necessary to solve each of the four problems in turn, while somehow leaving room for the abundance of non-ordinary matter implied by analysis of the Big Bang.
However, while the evidence for dark matter has been detailed above, we have yet to actually determine what dark matter really might be, or actually detect any dark matter directly. (This latter is hardly surprising; if, as appears most probable, dark matter is non-ordinary matter, it would by that very nature be extremely difficult to detect.) Still, nobody is going to be satisfied until dark matter is detected directly; until such time, alternative ideas will continue to be proposed and tested.