The proper motion of a star is the motion of the position of the star in the sky (the change in direction in which we see it, as opposed to the radial velocity) after eliminating the improper motions of the stars, which affect their measured coordinates but are not real motions of the stars themselves:
At first sight the stars seem to be in fixed positions with respect to each other, meaning they always form the same figures, and (for example) Ursa Major looks the same now as forty years ago. More careful observation shows that the constellations change shape very slowly, and that each star has an independent motion.
This motion is caused by the true movement of the stars relative to the Sun and solar system through space. It is measured by two quantities: the proper motion angle and the proper motion itself. The first quantity indicates the direction of the proper motion on the celestial sphere (clockwise from due North, East being left), and the second quantity gives the motion's magnitude, in seconds of arc per year.
Barnard's star has the largest proper motion of all stars, moving at 10.3 seconds of arc per year. Large proper motion is usually a strong indication that a star is relatively close to the Sun. This is indeed the case for Barnard's Star which, at a distance of about 6 light years, is, after the Sun and the Alpha Centauri system, the nearest known star to Earth (yet, being a red dwarf, too faint to see without a telescope or powerful binoculars, with an apparent magnitude of 9.54).
A proper motion of 1 arcsec/year at a distance of 1 light-year corresponds to a relative lateral speed of 1.45 km/s. For Barnard's star this works out to 90 km/s; adding in the radial velocity of 111 km/s gives a true motion of 142 km/s. True or absolute motion is more difficult to measure, as it depends strongly on the accuracy of the star's distance measurement. Currently, the nearby star with the largest space velocity (relative to the Sun's) is Wolf 424 which moves at the rate of 555 km/s. Only a little over half of the nearby star catalogue's stars have known true velocities.
Proper motion was discovered in 1718 by Edmund Halley, who noticed that Sirius, Arcturus and Aldebaran were over half a degree away from the positions charted by the ancient Greek astronomer Hipparchus roughly 1850 years earlier.