How does Thanos know where all the infinity stones are?

Question

In Avengers: Infinity War it seemed to me that Thanos (somehow?) always knew where the infinity stones were (except for the soul stone). Like he was using the space stone to get himself/teleport to the other stones' location all the time.

How does Thanos, conveniently, know where all the other infinity stones are, so he can go to that location?

Edit and clarification:
It's nice to see answered how he knew general location of the stones, but I was thinking more of how he knows exactly where they are.

For example (and as per answers):
He knows that Loki has the Space stone, but how does he know that Loki is in that spaceship?
He knows that the Time stone is on Earth, but how does he know that it is in New York?
He knows that the Mind stone is also on Earth, but how does he track Vision (in Scotland?) ? He even tracks him somehow when they take him to Wakanda. How?
Those were the things I meant when I said he knows where the stones are.

Answer 1

Quite possibly because he orchestrated things so that the stones would be revealed.

At the end of Age of Ultron when Thor is going to leave he says

Thor: I have no choice. The Mind Stone is the fourth of the Infinity Stones to show up in the last few years. That's not a coincidence. Someone has been playing an intricate game and has made pawns of us. But once all these pieces are in position...

Source: Transcripts Wikia > Avengers: Age of Ultron

consider also that it was Thanos which gave Loki the Staff which had the Mind Stone in it and had hired Ronan the Accuser to find Power Stone, or at very least the Orb know it was in it

Ronan: I promised Thanos I would retrieve the orb for him. Only then will he destroy Xandar for me. Nebula, go to Xandar and get me the orb.

Ronan: The orb is in my possession, as I promised. [Korath holds up the orb in his hand]
Thanos: Bring it to me.
Ronan: Yes, that was our agreement. [Ronan takes the orb from Korath] Bring you the orb, and you will destroy Xandar for me. However, now that I know it contains an Infinity Stone, I wonder what use I have for you.
Thanos: Boy, I would reconsider your current course. [Ronan opens up the orb and looks at the Infinity Stone inside]
Korath: Master! You cannot! Thanos is the most powerful being in the universe.
Ronan: Not anymore. [suddenly Ronan embeds the Infinity Stone in his warhammer and absorbs its power into his body] You call me "boy!" I will unfurl one thousand years of Kree justice on Xandar, and burn it to its core! Then, Thanos, I'm coming for you. [he ends his call to Thanos]

Source: Transcripts Wikia > Guardians of the Galaxy

also in Avengers: Infinity War it's revealed that

Thanos had sent Gamora out to find the Soul Stone and after capturing and torturing Nebula, learned that she had found it

while Power and Mind is easily explains we don't exactly know exactly how he knew where the Space Stone was at the time he sought it out or that the Reality Stone was at Knowhere in Taneleer Tivan's possession but given Thor's statement in Age of Ultron he may have orchestrated things in some so that he could find them more reliably as oppose to having had the Tesseract left on Earth and the Ether hidden away by Odin's father, Bor Burison.

as for the Time Stone, while we don't know if he had any hand with the Eye of Agamotto ending up in Kamar-Taj however i would suspect that he or the Black Order knew that either

a) Attacking the New York Sanctum would lure out Strange with the Time Stone

and/or

b) One could get to Kamar-Taj from the New York Sanctum as the Black Order landed in New York rather than Tibet

there is also the possibility that the Stones react to one another as they come together as

Vision's Stone start to react with him commenting that it was trying to warn him and Thanos only needed a couple of stones, the ones he knew where they were, in order to find the rest. however this might have been a unique property of the Mind Stone as Thanos still needed Gamora to reveal to him the location of the Soul Stone

Answer 2

Thanos is, and has been for some time, gathering information on the stones and their whereabouts. He's shown to have asked Gamora to locate the Soul Stone for him, and it stands to reason that he has asked either her or others in his employ to locate the rest of the stones.

Given that it's his "destiny" to control all of the stones, he will have made it his business to know everything about them and where to find them.

He knew the Power stone was on Xandar - he knew that was where Ronan had taken it and lost it to the Guardians of the Galaxy.

He knew the Collector had the Reality stone, though it's unclear exactly how he found that out. He did get it after the attack on the Asgardians, so perhaps he got that information through torturing them.

He knew the Mind stone was on Earth - he gave it to Loki to take there, in order to try and gain the Space stone. He was aware in the aftermath, that the space stone went to Asgard.

It's not entirely clear how he knows where the Time stone is, but the Eye of Agamotto has been with Earth's Sorceror Supreme for a long time (The Ancient One before Dr Strange), so it's entirely likely that it's generally known where that one is.

Answer 3

Through Ronan and Loki, Thanos at least has a good guess to the location of all but the soul stone.

He spent many years hunting down the stones and his desire to achieve his goal is what led him to forge deals with Loki and Ronan the Accuser in their respective campaigns against Earth and Xandar, as seen in his promising to aid them in exchange for an Infinity Stone. Both of these new alliances cost Thanos much of his resources, including one of the stones and the loyalty of his two daughters, Gamora and Nebula, and inadvertently resulted in the formation of the two superhero groups: the Avengers and the Guardians of the Galaxy. Fed up with these failures of his subordinates, Thanos opted to seek out the six Infinity Stones himself.

Ronan informed Thanos that he has The Orb (the power infinity stone) and that he’s going to Xandar with it based on his quote. That’s the first stone that Thanos recovers before Infinity War starts.

"I will unfurl one thousand years of Kree justice on Xandar and burn it to its core! Then, Thanos, I'm coming for you!” Ronan the Accuser to Thanos

It’s reasonable for Thanos to assume Loki may have the Tesseract based on the events in the first Avengers movie and Thor Ragnarok. We see he’s right at the start of Infinity War.

In 2012, after his defeat at the hands of Thor, Loki came into contact with the alien race known as the Chitauri, and their master, Thanos, who had already been seeking the Tesseract. Loki promised to retrieve it from Earth and give it to Thanos in exchange for his army. Through manipulation of the Tesseract's energy, Thanos teleported Loki to the Tesseract's location at the Joint Dark Energy Mission Facility.

When Loki went into Odin's Trophy Room to retrieve the head of Surtur, he passed by the Tesseract and took it from the vault.

I’m not sure how Thanos identified the Collector as having an infinity stone; but I would suspect the Collector in his own hunt for the other stones was not as careful as he should have been.

Once Malekith was defeated, the Asgardians managed to contain the Aether and, with the Power Stone already in their possession, feared having too many Infinity Stones in one place. Instead, they gave it to the Collector, who promised to look after it – not realising he intended to collect them all himself.

Given the failed invasion of New York and that Loki doesn’t have the scepter, Thanos can assume that the mind stone is still on Earth.

Thanos also provided Loki with a Scepter containing the Mind Stone.

It’s possible that Loki, Kaecilius or Dormammu conveyed to Thanos that the time stone is on Earth. Or given how long the time stone has been on Earth, Thanos could have known about it for centuries.

Strange wore it once again a little while later while meeting with Thor and Loki.

Thor’s vision is what makes me feel Loki had the knowledge about the time stone.

I won’t say I know completely how; but I will say Thanos had means of gaining this information.

Even if it isn't well explained, by the end of Avengers: Age of Ultron, it's clear what Thor learned. He's the first person to connect the gemstone dots.