Concur, the substitution facility is not part of the regular expression formalism proper.
The original implementation of regular expressions was by Ken Thompson in the QED (and later
ed) editor. Certainly, there was the s/re/p command in that already then, but his paper on regular expressions describes the "search" part and the underlying mathematical formalism, a concept called "regular sets" which is where the "regular" part in the name comes from.
Ken Thompson - Wikipedia, the free encyclopedia
Regular expression - Wikipedia, the free encyclopedia
K. Thompson,
Regular Expression Search Algorithm, Comm. Assoc. Comp. Mach., Vol. 11, 6, pp. 419--422, 1968.
(It's the very first article in his publications list at
http://www.cs.bell-labs.com/cm/cs/bib2html/ken.htm)