Acquisition of information itself cannot be accidental. You instinctively observe your surroundings and try to make sense of it. (The only exception I can think of is planting information in someone directly via modify memory.)
What would fit the style you are going for is putting the sources of information in ordinary places, but put the characters in the unique position of being able to acquire it "by happenstance". Either they are in just the right place at the right time ("You go to the outhouse behind the inn and notice through the window of one of the rooms the smith confessing to the noble's daughter. Ooh!") or they are the only ones able to deduce the information based on existing knowledge ("Horrible! People started disappearing from the town. Last week our smith, now the noble's daughter is missing too!").
The point is that the information acquired and their reason to enter the scene should not have much in common. You can even add scenes that you would skip otherwise (like going to the outhouse).
There are two routes possible: it is either truly random or you define an underlying structure. If it is random, you practically roll on a random encounter table whenever it seems appropriate, usually when they enter a new scene (maybe with two tables for abandoned and densely populated places). The other is much harder to pull off. Instead of rolling, the choice of information to give should make sense to you: "if they go up to the rooms in the inn during dinner, they see...". It can help in designing the adventure by forcing you to make sense of it and fill all possible gaps in logic. The problem is that the players by design will not know the difference. So if you are fine with a more narrativist approach, I recommend making the random tables. Going the other way only is much more work, even for seemingly simple plots. Of course a mix of the two approaches is possible too and is what you will end up with most likely.