There is an interesting timeline here which includes other transportation service as well.
According to this New York Times article, the FAA banned smoking on all flights under 2 hours beginning April 23, 1988. According to the timeline, Northwest and British Airways make all domestic service smoke free shortly after.
On February 25th, 1990, the rule is expanded to all domestic flights under 6 hours, which includes all but 28 of 16,000 flights.
In 1992, ICAO urges its members to go smoke free by July 1, 1996. Delta went smoke free on all flights starting in 1995. TWA, United, and American follow suit in 1997. In 1998 even more airlines go smoke free.
This federal rule bans smoking on all flights to and from the US and is effective June 4, 2000. It mentions that all domestic and 98% of international flights were already in compliance.
td;dr The FAA banned smoking on all flights under 2 hours in 1988, and it escalated from there. Within 10 years, almost all airlines were smoke free.
I think that smoking had the advantage of being a health issue, whereas electronic devices are more just convenience and comfort. Barring any emergent safety issues, it seems easier to allow people to do something new (use electronic devices) than stop them from doing something (smoking). Considering the proliferation and advancement of inflight entertainment systems, I would expect airlines to be fairly quick about allowing the use of devices, especially since some already do (I know American and United do).