It’s a matter of weeding out the right meanings and tracing them throughout the centuries.
The exact original meaning of the second element in again is not entirely sure. It can be confidently traced back to a Proto-Germanic *gagino- or *gagano-, which is most likely some kind of reduplicated formation based on the verb *ganganą- ‘to go’. It has various related, but different, meanings in the Germanic languages, but as best we can tell, the original meaning had to do with simple movement: straight, direct, flat-out, towards, etc.
From a meaning like ‘towards’ (which goes from just describing the ‘form’ of a movement to also including a target of the movement—a change from adjective to preposition) comes the secondary meaning ‘against’: if you move towards something in a straight, direct line, you are moving up against it.
This sense became the prevailing one of the preposition in more or less all Germanic languages, and as often happens with prepositions in Germanic languages, it became compounded with other prepositions. When prepositions are whittled away into small words with very broad meanings, it can be helpful to combine them with other prepositions to make their meaning more precise and clear; compare how upon (from up + on) is a bit more specific than just on. This probably happened already in Common Germanic for *gagino-, but quite freely: it wasn’t lexicalised until the very last stages of Common Germanic, or perhaps even later, in the individual languages.1
Various different prepositions were originally attached to *gagino- in this way: the old cognates of in and on were the most common, but and2 and even to are also found. Old English mainly generalised on, while Old Norse generalised in.
So at this point, at a very, very, very early stage of pre-Old English, you have pairs like *gegin ‘against, towards’ and *an gegine ‘against’, both meaning more or less the same thing. Later on, *an gegine loses its status as two separate words and some Old English sound changes take place, so you end up with things like onġeġn, onġæġn, onġēan, etc., where ⟨ġ⟩ is pronounced [j], like ⟨y⟩ in Modern English. Even later, the prefix on- is regularly reduced to a- when unstressed, which yields Middle English forms like ayēn, ayein, and so on.
When the Norse came along and had a great deal of linguistic effect in the North of the country especially, their form (which had not been affected by palatalisation and still had [ɡ]) influenced the inherited form, and Northern forms like ongēn, ongān, ongein (later agēn, agān, agein), etc., started popping up. These ended up being the ones that took over when English started becoming more unified as a language in late Middle and Early Modern English, which is why we now just have again, not †ayain.
At some fairly early stage, the meaning ‘against, towards’ started being used particularly in reciprocal terms: ‘against one another’. From this sprang a general meaning of reciprocation, and from that an abstract sense of ‘returning’ or ‘back to the original state’. It is possible that this development took place in Old Norse and was carried over into English when the Norse form was blended with the inherited English form—the same development is seen in Old Norse, at any rate.
This last sense is what we find in expressions like “young again”, where again indicates not so much repetition of an action, but a return to a former stage or state.
And from this last meaning, it is but a short semantic journey to arrive at the word again referring simply to something done, well, again. Simple repetition.
Helping this rather radical development along the way is of course the fact that, as with quite a few other words, the Old English genitival form onġēanes and similar forms survived as an alternative, yielding against (with the same extra t that also shows up in amongst and other forms). When you have two alternative forms of a word with no real difference in meaning, and a semantic shift is underway, a common strategy is for one word to retain the earlier meaning and the other to run with the semantic shift. In this case, against kept the original meaning, whereas again was abstracted, expanded, and redone semantically.
(The reason why it’s this way around is possibly that Old Norse did not have a form with an -s(t). If the development in meaning does really come from Old Norse, then it makes sense that it would be applied to the word in English that was obviously the same, but not to the word that looked different enough to be thought of as a different word.)
1 For ‘free’ and ‘non-free’ prepositional compounds, compare the difference between up on—which is just a combination of two prepositions and still means the sum of both of them (“The cat jumped up on the table”)—and upon, where the combination has been fossilised as a lexeme of its own and means something different from just the sum of its parts (“The cat jumped upon the table”).
2 And used to be a prefix and a preposition in English meaning ‘against’ (!). It is still very common as a prefix in German and Dutch, where it is ent- and ont-, respectively. It now only survives in English in a few words where it’s no longer recognisable as such, like answer (OE andswarian, from and- ‘against, back’ + swarian ‘swear, answer’).
