When was the Speed Trim System implemented on the Boeing 737?
Boeing's patent (US4676460A) for the STS was filed on 1984-11-28, the same day of the 737 Classic (3/4/500 series) entering service.

So since the addition of the bigger engines on the Classic, it's been there.

Below is from a 737 flight manual of a company that had both the Classic and NG at one time, which highlights the differences between the two series.

The 3 (for -300) in a circle is non-EFIS, in case you're wondering how the two 3's differ.