Adding a new program can mean creating a new domain. But even if this is not the case the process needed to get the new program running is quite interesting. It works basically like this: The SELinux security log is used to find all the "denied" access the program was not allowed to perform due to security policy reasons.
Step by step "allow" statements are added to the policy database (files) to give the program more rights. Sometimes a new domain should be created if the addition of a program to an existing domain would cause to many access privileges to be granted.
The whole process is not only cumbersome: it also shows an interesting software problem. Usually we are glad about interfaces which hide implementation details. Just think about distributed remote calls where a client only gets an interface and never knows what the server side will call to perform the request.
But with respect to security we need to know what a certain program will do during a request. Which resources will be accessed etc. Unfortunately this information is today not available once a program is ready for installation. But a mandatory access control system like SELinux needs exactly this type of information - and it should not be necessary to RUN a program to find the access right problems.