They are paid from the old crime fighting slider (now re-branded administration) and the amount of money you need to devote to administration is based on the number of bureaucrats your country has. At state level they affect tax collection and crime fighting, at national level how effective social reforms are. There is a maximum effect they have, but that won’t stop the bureaucracy growing leading to a possible bloated bureaucracy.
We felt that the tax collection ability was an important balancing factor in the game. As we mentioned in a previous developer diary we can use the number of bureaucrats as a way to balance out various countries, without having to resort to hard coded nerfs. However it also has another neat consequence... You have just claimed a colony, it is yours, you need to send troops off to defend it, etc. However, there is no administration there, leading to no revenue coming in to your country. Essentially, the colonial game will cost you money initially, however if bureaucrats emigrate to your colonies or if you are able to start creating a local bureaucracy then you will start to see money flowing in.