Have not tested this, but if you add the shortcuts to here C:\Users\Default\AppData\Roaming\Microsoft\Internet Explorer\Quick Launch then any new user that logs on to the system should get the customized icons.
I don't think there is a way short of doing a logon script to copy the shortcuts to that location in each user folder for any pofiles already on the system.
If you want to have any existing users to get the same shortcuts, you can add it to the Public Desktop or Start Menu.