There were many ways to discover moves.
Gamers would methodically try combinations with different characters to discover new moves. These spread by word of mouth amongst local communities, which further spread globally.
Media would publish marketing pieces from the studios, or similar material produced in house. Studios wanted to build hype around their product to improve sales, so they would put out marketing with character biographies and moves in magazines. The magazines themselves wanted to sell ads, so even if a studio was not paying for the material it was in their own interest to write material covering top games. Books, play guides, and similar were also available with varying degrees of studio involvement.
While the modern Internet world wide web as we know it today did not exist, the pre-web Internet was thriving. Enthusiasts had access to pre-web communications such as Gopher, IRC, and messaging forums to exchange information on any topic including gaming. This was also the heyday of BBS bulletin board systems, which individually may or may not have also linked various types of Internet sources with more local content. It was easy to publish or download a walk-thru or study guide for many games.
For Street Fighter II specifically I recall my roommate staying up for hours many nights reading forums and studying downloaded FAQs, then dropping quarters like a waterfall at the arcade during the day.