Those videos are 6 years old, much different versions of iTunes.
I click on the iPod Shuffle device icon, then go to music under settings, and click the check box next to Sync Music. That will bring up all your music and let you add music by Playlist, Genre, Band, Album, Artist, Song Title, etc. Put a check next to it adds it, unchecking it removes it. Then you just hit the Sync Button at the bottom left and it makes the changes on your iPod Shuffle.
Pretty much the same thing as adding music or movies to an iPhone or iPad.
I had the exact same issue but found the solution (on Mac OS Sierra, at least). In iTunes, you have to manually drag the music files from your iPod Shuffle into the trash bin. That deletes those files from the iPod, but the files don't wind up in Trash.