When Dumbledore first left Harry in the care of Petunia and Vernon, he invoked powerful protection charms to prevent the Death Eaters from finding Harry's location. At this point, it is assumed that Sirius Black is a Death Eaters. If that is the case, how was Sirius able to find Harry's house when it was supposed to have been protected? As Lily's friend, Sirius might have known the address, but the protection should've been stronger if it was known that Harry's location would be discovered - right?
I recall Dumbledore telling Harry that as long as he was with his kin, he was protected by love - until he would come of age at 17. I do not remember anywhere in canon that said Number 4, Privet Drive was under Fidelius.
It also could not have been protected because Ron had found the house with Fred and George in the beginning of CoS. Harry didn't ever tell Ron or Hermione his home address; he usually referred to it as Privet Drive, as Ron refers to his home as The Burrow, which is not the actual address.
I'm not aware of any answer from canon (books or interviews) but Sirius was one of the Marauders. He'd have known Lily extremely well (being James best friend and Harry's Godfather) and would have likely known that Lily's sister got married and to whom.
Also, I don't recall that Dumbledore actually hid Harry's location - the house wasn't under Fidelius.