In Avengers: Infinity War, Red Skull says that he had been searching for the Infinity Stones. The problem is that at the time that he is referring to he only knew about the Tesseract from Norse mythology, calling it "the Tesseract; the jewel of Odin's treasury". There is no indication he knew it was something more than a powerful Asgardian artifact; and there is really no way for him to have known about the Infinity Stones.
A lifetime ago, I too sought the stones. I even held one in my hand. But it cast me out, banished me here, guiding others to a treasure I cannot possess.
He sought a powerful artefact, the Tesseract, that he now knows to be an Infinity Stone. (We can assume the Soul Stone itself did the Basil Exposition work with the Red Skull off-screen.) Just because he didn’t know that the Tesseract was an Infinity Stone when he sought it, that doesn’t contradict what he’s saying.
Slightly more problematic is the plural “sought the stones”. In Captain America: The First Avenger, unless I’m forgetting something, we only saw him seeking the Tesseract.
I don’t think that’s fatal though. It’s entirely plausible that, during his time as a Nazi, he sought more than one legendary supernatural artefact. Legends of the other stones could have been present on earth via Asgard, or other alien civilisations, or have stemmed from the Time Stone — which, as far as we know, was in the custody of The Ancient One on earth for a long time.
It’s even possible (if unlikely, given what we know) that he was aware of the existence of Infinity Stones back when he was seeking the Tesseract, and had worked out it probably was one before he found it.
The absence of exposition on the part of The Red Skull revealing any knowledge of the true nature of the Tesseract, or of the existence of any other Infinity Stones, does not mean he has no knowledge of them. In CA:TFA, we learn that The Red Skull (Johann Schmidt) is obsessed with power, according to Dr. Erskine:
Abraham Erskine: Now Schmidt is a member of the inner circle and he is ambitious. He and Hitler share a passion for occult power and Teutonic myth. Hitler uses his fantasies to inspire his followers. But for Schmidt, it is not fantasy. For him, it is real. He has become convinced there is a great power hidden in the earth, left here by the gods, waiting to be seized by a superior man. So when he hears about my formula and what it can do, he cannot resist. Schmidt must become that superior man. Source
He obviously knows what the Tesseract is capable of, as he is able to instruct Dr. Arnim Zola on how to harness the power and develop the weapons we see in the movie. There is nothing that negates the idea that Schmidt has at least some information on the nature of the Tesseract, including the possibility that there are other powerful objects out there of its ilk. It seems that the Tesseract was simply the first item that Schmidt sought. It's entirely possible that he knew of, and had planned his next acquisition to be, the Eye of Agamotto.
You'll have to refer back to Captain America: The First Avenger for that. Remember, Red Skull grabbed a hold of the tesseract aka space stone, and ended up getting what we thought was vaporized. Apparently he was sent either in body or in spirit after the remaining stones. He could have gained knowledge of the rest from traveling the cosmos, or it might have been granted to him when he disappeared.