It kind of depends on your system design. You could do it at the Route Pattern by modifying the "Prefix Digits (Outgoing Calls)" field under Calling Party Transformations.
The other option is to use the BAT feature, but if you have any External Phone Number Masking it would be erased. Not sure about your system or version... In my CUCM 7x environment I would go to Bulk Administration -> Phones -> Add/Update Lines -> Update Lines. Then I would find whatever I needed to modify and only edit the External Phone Number Mask field. Remember to check the box to the left too.
