I would like to change our execution policy to "AllSigned" and use a self-signed certificate. I see all of the tutorials for creating a certificate in PowerShell, but I'm not sure what to do from there. What is the easiest way to run scripts on all machines with an execution policy of "AllSigned"? Do I need to push the cert out to all machines via Group Policy or another method? Can I use that same cert with all of my PowerShell scripts?
Using a self signed certificate is, sadly, a horrible idea. And difficult to use in the way you describe. It also doesn't confer any of the actual process benefits of signing, so it ends up being futile.
What you should do is set up a CA, which is included in Windows Server. Push the CAs root certificate to your clients via GPO, so they trust it. Issue a code signing certificate, and then shut the CA down. Ideally, make the CA a VM, and just store the VM files on a removable drive that you can lock in a fire safe for future need.
Of course, running a CA continuously gives you other great abilities that'll be helpful if you start doing DSC and stuff, but you can always get into that when need arises.