Google had sponsored links for as long as I knew about it, at least 2000. That section was at the top back then and is like that today, but there were times it was only on the right side.