They don't explain in the videos how an ordinary user is able to get a root shell via the exploit. Do all of the examples require a binary to be setuid in order to work?
Yes, in control flow hijacking exploits like these ones, you make a given process execute external code (typically a shellcode, i.e. a small piece of code which launches a shell). Any code executed this way runs with the UID of the original process, so a setuid root program is needed to get a root shell.