(grand)inquisitors gain valour by burning people, assassins by killing people (generals or other agents), spies gain valour by creating rebellions or opening castle gates. Don't know how bishops gain valor, but i think it is by converting people and make alliances.
You don't get stars for every succesfull action, it goes like this:
1 succes = 1 star
2 successes = 2 stars
4 successes = 3 stars
8 successes = 4 stars
...