Macros are stored server side.

However, when you log in to an existing toon, the game checks changes in the macros-cache.txt file in the WTF folder (either top level per account or in the character specific folder), then it will use those instead. You must then log out for those new changes to be stored server side. Same with chat and bindings.txt etc. However window positions are not always stored in any config file and usually you must set those manually. Add-in settings can usually be found in a corresponding lua file.

So to recap. Log out of WoW. Copy macros-cache to appropriate folder(s). Log toon(s) in and then out again.