I have a client who has a website with a styled google map showing locations of all their hotels, can I link to this on a Muse website I am creating for them so it appears within a page on the new site?
Yes, you can surely do that if got access to the embedable code of he map.
If I get the embeddable code would I just need to go to 'Insert HTML' and paste in there?
Yes correct, you will have to follow this in any method you choose from above.
I suggest also give a try to Cheeky71's suggestions as it looks quite simple and time saving.