I have created a new tag in Google Tag Manager and need to embed this on all pages in AEM.
Where do I do this?
You would need to add the JS code into the page template. All the web-pages created with this template would then be having GTM implemented in it.
Try adding the required JS libs to a clientlibs in your AEM project - as mentioned by Kautuk