In news, radio shows and other rather formal podcasts I keep hearing 改めまして at the begining of the program or broadcast, but I can't find an explanation of what Japanese people mean by it. I did find something that said "doing things formally" but that doesn't help much. Any help is appreciated.

Apparently it means much the same thing as 「あらためて」 but there is a fuller explanation here for exactly the usage you're asking about: http://torokko.sblo.jp/article/2643584.html

Thanks so much for the link. Just skimming it seems that the common usage of this word in radio shows is somewhat weird for the Japanese themselves.