Professor Trelawney's second prophecy turns out in some ways to be almost as significant as her first. Crucially, it gives Harry and everyone connected with him a key heads-up notice period where they know that Voldemort will rise again. (Presumably, Harry and Dumbledore are aware of this before even Voldemort himself is). Harry clearly tells Dumbledore about the prophecy at the end of Prisoner of Azkaban:
"Professor Dumbledore - yesterday, when I was having my Divination exam, Professor Trelawney went very - very strange."
"Indeed, "said Dumbledore. "Er - stranger than usual, you mean?"
"Yes...her voice went all deep and her eyes rolled and she said...she said Voldemort's servant was going to set out to return to him before midnight...she said that the servant would help him come back to power." Harry stared up at Dumbledore. "And then she sort of became normal again, and she couldn't remember anything she'd said. Was it - was she making a real prediction?"
Dumbledore looked mildly impressed.
"Do you know, Harry, I think she might have been," he said thoughfully. "Who'd have thought it? That brings her total of real predictions up to two. I should offer he a pay rise..."
"But -" Harry looked at him, aghast. How could Dumbledore take this so calmly?"
Prisoner of Azkaban, Chapter 22, Owl Post Again
Dumbledore's immediate response is to console Harry that Wormtail escaping wasn't his fault. OK, good job comforting the insecure teenager, Dumbledore. No need to alarm Harry that his evil nemesis may be on the way back. However, after that conversation you would expect him to go straight up to his office, reform the Order, notify the Ministry and try to get to Voldemort ahead of Wormtail. "All hands on deck. We're going to Albania, guys."
His response is especially criminal in the light of the fact that he basically knows where Voldemort is:
"What interests me most," said Dumledore gently, "is how Lord Voldemort managed to enchant Ginny, when my sources tell me he is currently in hiding in the forests of Albania."
Chamber of Secrets, Chapter 18, Dobby's Reward
Dumbledore has sources. Wormtail only has rumours and rat-friends. Womtail may have had a few hours head-start but you would bet on Dumbledore and the Order managing to get there first.
When Harry goes to visit Dumbledore in Goblet of Fire he gives Dumbledore the information that Wormtail has indeed managed to find Voldemort and that Voldemort is getting stronger, strong enough to hold a wand (additionally, Snape's Dark Mark was becoming stronger). This is the confirmation that Voldemort's return is a real risk but at this point he is already in hiding. The crucial point at which Dumbledore could have headed Wormtail off was at the end of Azkaban.
Assumption: Dumbledore or anyone else wouldn't have been able to do much to Voldemort in his bodiless spirit-form. Voldemort was already deprived of a body and so was essentially powerless at this point. Voldemort later says that "The Aurors were still abroad and searching for me." What those Aurors would've hoped to achieve isn't clear since spirit-Voldemort could just swoosh away somewhere else. Only once Wormtail found him was Voldemort a threat.
So why didn't Dumbledore do more in response to Trelawney's prophecy? Did he just assume that Voldemort was going to come back anyway, regardless of what he might do to prevent it?