How new is ctrl+r?

Old.

It's not a Linux thing. The feature you're talking of belongs to the bash shell via the readline library that it uses. It will work identically wherever you can get bash to run, including Windows, the BSDs, OSX, etc.

It's been part of Bash since at least version 1.14.7 (from 1995), since the manpage of that version mentions reverse-search-history much the same way today's manpages do. You can check the source from the GNU repository.

It's also mentioned in the FEATURES file of bash-1.05, which apparently is from 1990.

It originates with Emacs, not bash so it probably goes back to 1983 at least, if not 1975.