Old English ærning, "act of one who or that which runs, rapid motion on foot," verbal noun from run (v.). Of a ship, "the action of sailing," 1680s.
Colloquial phrases in (or out) of the running "among (or not among) the lead competitors, competing (or not competing) in a race" (1863) is a metaphor from horse racing, where make the running "set the pace" is recorded from 1837; hence "likely to succeed." Running-shoe is from 1884.
"that runs, capable of moving quickly," late 14c., rennynge, present-participle adjective from run (v.), replacing earlier erninde, from Old English eornende. The meaning "rapid, hasty, done on the run" is from c. 1300. The sense of "continuous, carried on continually" is from late 15c.
Running-jump is from 1914. A running-mate (1865) originally was a horse entered in a race to set the pace for another from the same stable who was intended to win; U.S. "vice-presidential candidate" sense is recorded from 1888. Running-board is attested by 1817 in reference to a narrow gangway on either side of a ship or boat; extended by 1907 to the footboards of cars and trucks.
Running dog is recorded by 1937, from Chinese and later North Korean communist phrases used to describe supposed imperialist lackeys, such as Mandarin zou gou "running dog," on the notion of a dog that runs at its master's command.