It used to be client-sider and saved in a macros-cache.txt and macros-local.txt file. Now I have no idea.

Edit: They are saved in a file in your wowfolder, more precisely:
HDD:\WoWfoldername\WTF\Account\accountname\realmna me\charname

and in there you find the file "macros-cache.txt".