yes, you can add your logo.
when you add an image into your template mxd, it gets added by reference using the path. In your case, the reason it is not drawing is most likely because the ArcGIS Server account does not have access to that folder.
this is what we usually recommend. After adding an image on the layer, open the Properties of the image, switch to 'Picture' tab and check 'Save Image as a Part of Document' option.
this should do it for you.