You do not generally need a PNG file, any image format will do as long as:
1. The background color is one that can be set to ...'be hidden' in the Effects >>Video effects >> Chroma key menu.
2. The transparent color does not appear in your logo.
If your logo is multi color then PNG is the way to go as it can contain a 'mask' layer which specifies which parts of an image are transparent irrespective of their color. I'm sure you'll get help on that from others, I've not used it enough to half remember how. The method may be specific to your graphics editing program.
If I do it the way you say, When I have the logo in my MPEG 4 film do I save it again as MPEG 4 because I deleted the original clips, I didn't think I would need them again, So I converted them to MPeg4 ready for You Tube.
This comes from a previous post where I recommended you use a png file. You can use Carls method however I prefer to keep things as simple as possible and avoid possible problems ie :-
Chromakey is not necessary with a transparent background png file.
png with transparent baclground eliminates all possibilites of colour fringing
Depending on which image editting program you have - start a new image of the size you require and set the background (colour) to transparent , add in your logo text/shapes etc then save or export the image as a png file