2.1. The Beginnings of the Dark Matter Problem and Rotation Curves
The dark matter problem is perhaps the longest outstanding problem in all of modern physics. The puzzle dates back to the 1930's, to the work first of Knut Lundmark in Sweden and shortly after that Fritz Zwicky at Caltech. Zwicky noticed that galaxies in the Coma Cluster were moving too rapidly to be explained by the stellar material in the cluster. He postulated that additional mass in the form of something dark must be providing the gravitational pull to speed up the orbits. Subsequent work continued to find similar evidence, but it wasn't until the work of Ford and Rubin  in the 1970's that the same unexplained rapid orbits were found to exist in every single galaxy. At that point the scientific consensus for dark matter emerged. For a review of dark matter history, see the review of Ref. 3.
Rotation curves of galaxies are flat. The velocities of objects (stars or gas) orbiting the centers of galaxies, rather than decreasing as a function of the distance from the galactic centers as had been expected, remain constant out to very large radii. Similar observations of flat rotation curves have now been found for all galaxies studied, including our Milky Way. The simplest explanation is that galaxies contain far more mass than can be explained by the bright stellar objects residing in galactic disks. This mass provides the force to speed up the orbits. To explain the data, galaxies must have enormous dark halos made of unknown ‘dark matter.’ Indeed, more than 95% of the mass of galaxies consists of dark matter. This is illustrated in Fig. 1, where the velocity profile of galaxy NGC 6503 is displayed as a function of radial distance from the galactic center. The baryonic matter which accounts for the gas and disk cannot alone explain the galactic rotation curve. However, adding a dark matter halo allows a good fit to data. 1
Figure 1. Galactic rotation curve for NGC 6503 showing disk and gas contribution plus the dark matter halo contribution needed to match the data.
The limitations of rotation curves are that one can only look out as far as there is light or neutral hydrogen (21 cm), namely to distances of tens of kpc. Thus one can see the beginnings of dark matter haloes, but cannot trace where most of the dark matter is. The lensing experiments discussed in the next section go beyond these limitations.
2.2. Gravitational Lensing
Einstein's theory of general relativity predicts that mass bends, or lenses, light. This effect can be used to gravitationally ascertain the existence of mass even when it emits no light. Lensing measurements confirm the existence of enormous quantities of dark matter both in galaxies and in clusters of galaxies.
Observations are made of distant bright objects such as galaxies or quasars. As the result of intervening matter, the light from these distant objects is bent towards the regions of large mass. Hence there may be multiple images of the distant objects, or, if these images cannot be individually resolved, the background object may appear brighter. Some of these images may be distorted or sheared. The Sloan Digital Sky Survey used weak lensing (statistical studies of lensed galaxies) to conclude that galaxies, including the Milky Way, are even larger and more massive than previously thought, and require even more dark matter out to great distances.  Again, the predominance of dark matter in galaxies is observed.
A beautiful example of a strong lens is shown in Fig. 2. The panel on the right shows a computer reconstruction of a foreground cluster inferred by lensing observations made by Tyson et al.  using the Hubble Space Telescope. This extremely rich cluster contains many galaxies, indicated by the peaks in the figure. In addition to these galaxies, there is clearly a smooth component, which is the dark matter contained in clusters in between the galaxies.
Figure 2. Left: The foreground cluster of galaxies gravitationally lenses the blue background galaxy into multiple images. Right: A computer reconstruction of the lens shows a smooth background component not accounted for by the mass of the luminous objects.
The key success of the lensing of dark matter to date is the evidence that dark matter is seen out to much larger distances than could be probed by rotation curves: the dark matter is seen in galaxies out to 200 kpc from the centers of galaxies, in agreement with N-body simulations. On even larger Mpc scales, there is evidence for dark matter in filaments (the cosmic web).
2.3. Hot Gas in Clusters
Another piece of gravitational evidence for dark matter is the hot gas in clusters. Fig. 3 illustrates the Coma Cluster. The left panel is in the optical, while the right panel is emission in the X-ray observed by ROSAT.  [Note that these two images are not on the same scale.] The X-ray image indicates the presence of hot gas. The existence of this gas in the cluster can only be explained by a large dark matter component that provides the potential well to hold on to the gas.
Figure 3. Coma Cluster: without dark matter, the hot gas would evaporate. Left panel: optical image. Right panel: X-ray image from ROSAT satellite.
2.4. Bullet Cluster
An image (shown in Fig. 4) of the Bullet Cluster of galaxies (a cluster formed out of a collision of two smaller clusters) taken by the Chandra X-ray observatory shows in pink the baryonic matter; in blue is an image of the dark matter, deduced from gravitational lensing. In the process of the merging of the two smaller clusters, the dark matter has passed through the collision point, while the baryonic matter slowed due to friction and coalesced to a single region at the center of the new cluster. The Bullet Cluster provides clear evidence of the existence of two different types of matter: baryons and dark matter behave differently.
Figure 4. The Bullet Cluster: A collision of galactic clusters shows baryonic matter (pink) as separate from dark matter (blue), whose distribution is deduced from gravitational lensing.
Thus the evidence that most of the mass of galaxies and clusters is made of some unknown component of dark matter is overwhelming. As I've shown, dark matter shows its existence gravitationally in many ways, including rotation curves (out to tens of kpc), gravitational lensing (out to 200 kpc), hot gas in clusters, and the Bullet Cluster.
Additionally, without dark matter, large scale structure could not have formed by the present time and we would not exist. Until recombination at z = 1100, the universe is ionized, baryons are tied to photons, and both photons and baryons stream out of structures as they are forming. It is the dark matter that clumps together first, before recombination, and provides the potential wells for the ordinary matter to fall into at a later time. In order for dark matter to initiate the formation of galaxies and clusters, it must be cold rather than hot. Hot dark matter would be moving relativistically and would stream out of structures in the same way that photons do; hence it was already known in the 1980s that neutrinos cannot provide the potential wells for structure formation and cannot constitute the dark matter. Nonrelativistic cold dark matter has become the standard paradigm for the dark matter in the universe. 2
Below I turn to the cosmic microwave background which provides irrefutable evidence for dark matter.
1 It is interesting to note that alternative scenarios without dark matter began with modified Newtonian dynamics (MOND).  While these models have been shown to fail, particularly by cosmic microwave background observations, they may provide an interesting phenomenological fit on small scales.  Back.
2 Alternatives do exist including warm dark matter. Back.