The Japanese emoticon, (^_^), was published by Yasushi Wakabayashi in June 1986 on ASCIInet. The user binbou was using the (‾_‾) emoticon around the same time. Japanese emoticons are also called kaomoji. More info here and here.
:-) and :-( were first made on a computer by Scott E. Fahlman in 1982. Some say they date back as long as 1862 or 1648. Also see the PLATO emoticons/emojis from the 1970s, and the Polish vertical emoticons from 1881.
More emoticon-posts here.
Update, June 2024: There is a text credited to Takeshi Kitano, 1970, that includes emoticons, but it was apparently a joke from 2009.