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.
Use the Generic Tracker cloud configuration in AEM, add your tracking code and include this cloudservice to your content hierarchy and you should be good to go.
(1) : Analytics with External Providers
Try adding the required JS libs to a clientlibs in your AEM project - as mentioned by Kautuk