First (as I've already done), add your domain alias:
Then, using zmprov again, add the aliases to your users:
> zmprov createDomain example.com \
zimbraDomainType alias \
zimbraMailCatchAllAddress @example.com \
This does seem to confuse the Zimbra Admin Console "Aliases" page when editing a user account, so you'll end up having to manage all the aliases via the command line if you don't want Zimbra Admin Console to freak out about the aliases. However, away messages will now be sent for all aliases.
> zmprov addAccountAlias <user>@<domain> <user>@<domain_alias>
> zmprov addAccountAlias <user_alias>@<domain> <user_alias>@<domain_alias>
Again, this is on 4.5.11 NE.