Here is a rough historical overview:

- 1900: Ricci and his student Levi-Civita introduce the concept of a "tensor" in

MR1511109 Ricci, G.; Levi-Civita, T. Méthodes de calcul différentiel absolu et leurs applications. (French) Math. Ann. 54 (1900), no. 1-2, 125--201.

There they define an operation called "covariant differentiation" of a tensor which generalizes the usual differentition to curvelinear coordinates; the correction term is given by the Christoffel symbols. By that time there is no abstract notion of covariant derivative of a section or whatsoever nor the differentiation is considered together with the associated parallel transport. For more about this I would refer you to the book by Morris Kline on the history of mathematics. There is also an edited edition of this article available (Editor is Hermann who was already mentioned by Deane Yang). Whitney used the word "tensor" in connection with a group theoretic construction in 1938 (he obviuosly was influenced by what he knew about tensors; see end of the paper where he speaks about parallel transport which gives an impression on how people thought about thing like that in the 1930's). Later this was generalized to modules by Cartan and Dieudonné (see Weibel's history on homological algebra).

Meanwhile Einstein and his friend Grossmann used this "absolute differential calculus" (as it is also called) to give a mathematical footing to general relativity. Later Einstein had a lot of correspondence with Levi-Civita as well as Cartan on topics like parallel transport which can be found in their scientific correspondence.

- 1917: Levi-Civita, T. Nozione di parallelismo in una varietà qualunque e conseguente specificazione geometrica della curvatura riemanniana. (Italian)
Palermo Rend. 42, 172-205 (1917).

Here Levi-Civita gives, following an indication of his teacher Ricci, a geometric interpretation of the covariant differentiation by means of a associated parallel transport. I only know of the italian version of this article but there is book of Levi-Civita (from the 1930s?) on tensor analysis where he gives a more or less plausible derivation of this concept; though I found it hard to follow in all details. Felix Klein by the way was not very happy with the derivation given by Levi-Civita and in some book (currently I can not recall the title but it is about geometry and also available in English) he derived the whole thing from a physical experiment with some peculiar machine which can be used to detect curvature. I think the books title must be something like "Higher Geometry". The idea seems to be due to Radon (1918); but seemingly published nowhere else. Anyhow the review by Blaschke (one of the leading person in differential geometry at this time) for the Zentralblatt is very illuminating (almost a prophecy).

between 1917 and 1920 (third German edition is published in 1919) Weyl published "Raum, Zeit, Materie" ("Space-time-matter"; available here: http://www.archive.org/details/spacetimematter00weyluoft). There he uses the Christoffel symbols and their transformation behaviour to define "connection". Around the same time as Levi-Civita, Schouten and Hesse made similar observations. This can be found in an easy to find article by acclaimed German mathematics historian Karin Reich. Unfortunately, this article is in German. Nevertheless you can see pictures of models of surfaces with parallel transport drawn on them, that Schouten produced. Later Weyl in connection with his physical studies introduced the concept of a Weyl connection (whose most peculiar property is that it does not preserve length); this was already mentioned in the comments. More can be found in Chapter I of this brilliant book (again German would be required): http://books.google.de/books?id=oZLiqDQGnjgC&printsec=frontcover&dq=Scholz+and+Weyl&hl=de&ei=IcVfTeSULILXsgaRz422CA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCoQ6AEwAA#v=onepage&q&f=false

Around 1923 Élie Cartan starts to study connections (his so-called projective connections) More on this can be found in the splendid article "Vector bundles and connections in physics and mathematics: some historical remarks" by Varadarajan.

Somewhere behind 1940 Norman Steenrod introduces the concept of a fibre bundle and
around 1950 Charles Ehresmann introduces the concept of a connection on a fibre resp. principal fibre bundle. His article is very readable and a valuable historical source.

1more comment