Don't quote me on this, but I believe its every time you add on a number of HD equal to their starting HD, increase its CR by 2. (Aka, a 3 HD, CR 2 creature advanced to 6 HD would be a CR 4 creature).
The DMG (pg. 102, under "Tougher Monsters") says that for every 50% that you bump up the HD by, raise the CR by 1. The XP award also changes proportionately, as a result.
This is one of those complaints about the CR system. It seems that it doesn't give the correct results in certain cases, especially in the case of some the outsiders...