Most orbital debris eventually re-enters the atmosphere. The vast majority of this burns up on re-entry, and only a small proportion of what's left lands on the surface.
Of that small proportion, the majority will land in the ocean (there is a lot of ocean!), and a fair chunk of the rest is probably never found, or just never identified. Nonetheless, every year or two something is turned up, and occasionally it's very dramatic.
When was the first time an object was found and identified as re-entering debris? I've been able to find a reference to a probable case in 1964 - Cosmos 50, which apparently had debris recovered in Malawi, discussed on p. 30 here - but nothing as yet from earlier. There were a number of cases as early as 1960 when debris from sub-orbital second stages were found in unusual places, but that's not quite the same question...