This can easily be answered by a line in Guardians of the Galaxy.
The Other talks to Ronan and tells him that Thanos' sources have revealed Gamora's plans to sell the Orb.
This tells the audience that Thanos has spies and agents throughout the galaxy keeping tabs on things.
In Age of Ultron he decided that instead of staying behind and just having his minions bring the stones to him while he sits on his throne, he would join the hunt himself. Before getting the stones however, he wanted to make sure they were all attainable first. This is why he waited until Nebula revealed that Gamora knew where it was. Once he knew where all of them were, then the hunt would begin. Whereas before having his minions take them forehand would've been a problem for two reasons
1). What if all six weren't able to be found, which was the case until the Soul Stone's location was revealed. Then his quest wouldn't have mattered since he can't attain all of them.
2). Having his crew hunting for them early on without him proved to be a failure as the last two time where he had someone else fetch the stones without him at their side, they failed. Whereas now, with him joining the hunt as we see in Age of Ultron where he says "Fine, I'll do it myself", it will increase his chances of completing his goal, now that he's actively participating.
He knows the Mind Stone is on Earth because of Loki's failure when using it during Avengers 1. He sent Proxima and Corvus to track the stone down, which they did, until Vision escaped, and they tracked him down to Wakanda by keeping tabs and following him.
The Power Stone, he knows Ronan took it to Xandar and it was being kept by the Nova Corps.
Soul Stone, he knew Gamora knew the location and forced her to tell him.
Time and Reality Stones, since he has spies and agents keeping tabs on the stones, he could've found it on Earth/Knowhere because of that. It's also possible that he could've tortured that info about the Reality Stone from Thor, since he knew where it was.
Space Stone, Thanos knew it was taken back to Asgard, and once the opportunity presented itself (once he knew where ALL of them were) he went there only to find Asgard destroyed, and he tracked down Thor and Loki's ship.
There's also one thing to keep in mind. The stones are actually alive, or at least have some form of sentience. They communicate with each other, which is how Loki teleported to Earth in Avengers 1, he used the Mind Stone to communicate with the Space Stone and allow him to instantly teleport to Earth.
[EDIT - It wasn't the stone that did this, but Loki mind controlling Selvig to build a machine to do that.]
Same with the Tesseract in The First Avenger. For abusing the Space Stone's power, the stone banished Red Skull to Vormir, and it communicated with the Soul Stone in order to transport him there.
In Age of Ultron Bruce and Stark discover the Mind Stone is sentient, and want to use it's power to create Ultron.
Plus, the Soul Stone requires a sacrifice of what you love, Red Skull even says that the Stone itself demands a sacrifice. Plus Red Skull referred to the stone as "Soul" and that it has "a special place among the Infinity Stones. You might say it has a certain wisdom." He's personifying the stone. This further shows how the stones are alive and not just objects
I bring this up because in the scene where Thanos states in Infinity War, "There are two more stones on Earth" the Space Stone was glowing, which indicated he was using it.