Following his eviction (of sorts) from Hogwarts it isn't clear where Dumbledore heads off to. The only place he rules out is Grimmauld Place.
"Where will you go, Dumbledore?" whispered Professor McGonagall. "Grimmauld Place?"
"Oh no," said Dumbledore, with a grim smile. "I am not leaving to go into hiding. Fudge will soon wish he'd never dislodged me from Hogwarts, I promise you."
(Order of the Phoenix, Chapter 27, The Centaur and the Sneak)
Yet we don't see Dumbledore again until he turns up at the Ministry at the book's end. There are various places he could have gone to escape the Ministry but few that would be in keeping with his intention not to go into hiding.
I found a discussion thread that mooted the concept that Dumbledore went Horcrux-hunting, which would at least explain how he was able to destroy the Peverell ring so quickly that summer. However, that would not present any sort of problems for Fudge. Dumbledore explicitly says that he will set out to make life difficult for Fudge. So presumably Dumbledore would go somewhere in keeping with that aim.
So is there any confirmation on where Dumbledore went? Indeed, is there any indication that he actually did anything which made Fudge regret dislodging him from Hogwarts?