I don't know the full history, but a bit of searching shows that linear feedback shift registers were in use in the 1960s, so it's a pretty old technology.
I have found that "River Raid" (1982) and "The Sentinel" (1986) were using it for game data. Apparently, the original "Elite" was supposed to use one, too, but they decided against it.