In the Harry Potter and the Chamber of Secrets, Dumbledore says that his sources tell him that Voldemort is hiding in Albania.
“What interests me most,” said Dumbledore gently, “is how Lord Voldemort managed to enchant Ginny, when my sources tell me he is currently in hiding in the forests of Albania.”
Harry Potter and the Chamber of Secrets - Chapter Eighteen
Clutching at straws a bit, but there are clues that point to Albania as a base for Voldemort before his resurrection:
Quirrell came across Voldemort while travelling in Albania.
We know that Quirrell took a sabbatical to travel and get some first-hand experience. Although Dumbledore might not have known the details upon his return, once he knew Quirrell had met Voldemort on his travels, he’d scrutinise the trip more carefully.
Hagrid tells us that Quirrell’s nervous demeanour began while on that trip:
“Oh, yeah. Poor bloke. Brilliant mind. He was fine while he was studyin’ outta books but then he took a year off ter get some first- hand experience ... They say he met vampires in the Black Forest and there was a nasty bit o’ trouble with a hag – never been the same since. Scared of the students, scared of his own subject – now, where’s me umbrella?”
— Philosopher’s Stone, chapter 5 (Diagon Alley)
So by talking to people who’d met Quirrell on his trip, you’d be able to get a rough idea of where he ran into Voldemort.
Since Voldemort was severely weakened by his encounter with Harry, it's not a stretch to imagine that he might return to Albania, rather than try to start somewhere entirely new.
Voldemort was possessing animals while in Albania.
We later learn that this is how Wormtail tracks down Voldemort:
Wormtail has a curious affinity with rats, do you not, Wormtail? His filthy little friends told him there was a place, deep in an Albanian forest, that they avoided, where small animals like themselves had met their deaths by a dark shadow that possessed them….
— Goblet of Fire, chapter 33 (The Death Eaters)
Dumbledore isn’t an Animagus, but he does keep his ear to the ground – rats may not have been the only animal being possessed. This may well have been noticed by officials in Albania as evidence of dark magic, but without harm to human life or evidence of a greater threat, filed away and forgotten.
If Dumbledore already has a suspicion about Albania, he’d be looking for this sort of small clue of Voldemort’s presence.
Was Voldemort the only magical resident of the forest? Perhaps not.
Maybe Dumbledore wasn’t talking to rats, but he can talk probably to centaurs, vampires, and other such creatures that live in forests. We know that magical creatures can live in Muggle forests (e.g. Erklings originate from the Black Forest) – maybe Voldemort’s Albanian forest had other magical residents, who‘d be able to tell Dumbledore (or somebody) of their unease in parts of the forest.
When the Dark Lord is returned to a corporeal form, he says that Wormtail looked for him in the country it had long been rumored he was hiding. Though Wormtail was helped by rats, the rumors gave him a place to start, and they’d apparently existed for some time before Wormtail‘s search.
“He sought me in the country where it had long been rumoured I was hiding … helped, of course, by the rats he met along the way. Wormtail has a curious affinity with rats, do you not, Wormtail? His filthy little friends told him there was a place, deep in an Albanian forest, that they avoided, where small animals like themselves had met their deaths by a dark shadow that possessed them …”
- Harry Potter and the Goblet of Fire, Chapter 33 (The Death Eaters)
These rumors may have already existed by the time Dumbledore mentions it. Though it was about two years after Dumbledore had already said it, Sirius was less connected than Dumbledore but also knew of the rumors that the Dark Lord was hiding in Albania.
“Exactly … she disappeared in Albania, and that’s definitely where Voldemort was rumoured to be last … and she would have known the Triwizard Tournament was coming up, wouldn’t she?”
- Harry Potter and the Goblet of Fire, Chapter 19 (The Hungarian Horntail)
Dumbledore most likely heard these rumors as well, and probably followed up on them to see if they were indeed true in whatever way he could.
As for who exactly his sources may be, the J.K. Rowling writing on Pottermore about Remus Lupin mentions that he knew that Remus was a werewolf because he had spies among Dark creatures who told him.
Dumbledore explained to the Lupins that he knew what had happened to their son. Greyback had boasted of what he had done and Dumbledore had spies among Dark creatures.
- Remus Lupin (Pottermore)
If any of these creatures who were Dumbledore’s spies knew the Dark Lord’s location, they’d likely relay it to him. They’d probably know this, and before word reached the wizarding world. In addition, if his sources were Dark creatures, that could be why he didn’t give more details. They might know this because some of them might either live in or associate with creatures who live in the Albanian forest where the Dark Lord was hiding. The centaurs in the Forbidden Forest near Hogwarts knew when he was hiding in their forest, and also knew who he was.
“Do you not see that unicorn?’ Firenze bellowed at Bane. ‘Do you not understand why it was killed? Or have the planets not let you in on that secret? I set myself against what is lurking in this Forest, Bane, yes, with humans alongside me if I must.”
- Harry Potter and the Philosopher's Stone, Chapter 15 (The Forbidden Forest)
Although at the time, almost no one at Hogwarts would have known that the Dark Lord was hunting unicorns in the forest by their school, but the centaurs knew, and they knew both who he was and of his plan to steal the Philosopher’s Stone.
“The Philosopher’s Stone! Of course – the Elixir of Life! But I don’t understand who –’
‘Can you think of nobody who has waited many years to return to power, who has clung to life, awaiting their chance?”
- Harry Potter and the Philosopher's Stone, Chapter 15 (The Forbidden Forest)
It’s possible that something similar occurred with the creatures in Albania. The rats certainly knew, so creatures that could communicate with humans (or Dumbledore specifically, since Dumbledore speaks the languages of certain magical creatures) may have known.
