How can I take approximately 50 company names, and have their headquarters plotted on a map?
If that's not possible: Assuming I had the addresses, how could I plot all those addresses on a map?
What (kind of) software should I use?
If you have a basic knowledge of programming you can look at the Google Maps API and embed it into a website or write a sample app to do what you need.
Otherwise you can use Goole Earth which allows you to map multiple locations on a map