Samurai Shodown would show special move commands when the CPU did them under the life bar. With street fighter, there were only 4 commands so you just tried them all with kick and punch and you know them all. Quarter Circle, Dragon Punch , charge back to forward, charge down to up
Mostly though, I think people got the move lists from game magazines and start up internet sites like SegaSages.com