The Melbourne Shuffle grew from a combination of girls doing Ballet/Tap dance and BBoys break dancing, with new steps thrown in.
Most girls in Melbourne learn social dancing from a young age and Tap dancing is a normal part of the dance lessons. The word Shuffle as a dance style actually comes from the Tap dance genre.
Here's some great old movie clips of the sort of dance steps the girls learned, and then showed the BBoys at underground dance parties in the early 1990's in Melbourne. There's some brilliant professional dancers here such as the legend "Rubber Legs" Al Norman.
It's worth remembering that these old movies were made just a year or two after sound was added to film - The Talkies. People would sing along in the cinema with the tunes. So if you feel inclined, you can sing along with them in front of your computer. After all, most shufflers dance along to shuffle clips in front of their computer these days :)
Penny Singleton and "Rubber Legs" Al Norman perform this dance number to the song "Good News" From 1930 . The music is played by Abe Lyman and his Orchestra.
An interesting move here in this first still from the vid. Somehow it never really caught on as a Melbourne Shuffle move. One can only wonder why :)
Check out the 1930's phatties
Some classic shuffle sideways moves
Mass Running Man
Good News 1930
With Abe Lyman and his Orchestra, Nancy Carroll, (Rubber Legs) Al Norman and Skeets Gallagher. From 1930 " Dancing To Save Your Sole
Dancing To Save Your Sole 1930
and the famous The Charleston
The Charleston 1920's