It is generally assumed that market prices follow random walks, implying market efficiency. However, one could find that some combinations of the "random walks" are cointegrated.
Does this contradict market efficiency? How should it be interpreted?
There's no contradiction.
Intuitively speaking the Market Efficiency Hypothesis has more to do with "predictability". In all of its three senses, it's more or less a translation of "you cannot make positive return consistently", in other words, as long as you're in the market, the next realization of return is no more than random draw, i.e. returns are non-predictable.
Now that's what we would call things happening along the time line. But if we fixed the time point, and go into cross-sectional data, then there's a good chance to find relationship that is both statistically significant as well as give you good explanation power(in terms of fitting data). The easiest one you can think of is CAPM: $$r_i - r_f = \beta_i(r_m - r_f)$$ well, this might be leap of faith..But this is nothing more than a cointegration relationship..
So that does this say then? It means that you cannot predict what happens tomorrow(EMH), but you whatever it happens tomorrow, there could possibly exists a relationship across assets.(Cointegration) Remember the randomness are for all assets, but there could some underlying factors which drive all the returns, which then gives you a factor model.
So as an example, you buy and sell the same stock for one share, I don't know what the stock price is going to be tomorrow, but I sure know that my payoff is even. And that's it.
Cointegration does not contradict market efficiency. On the contrary, lack of cointegration where it is due would contradict market efficiency. For example, if the same stock had noncointegrated prices across different exchanges (e.g. NYSE vs. NASDAQ), only one of them could reflect all available, relevant information, and the others would not.
Why is this a relevant argument? From Investopedia:
Market efficiency refers to the degree to which stock prices and other securities prices reflect all available, relevant information.