The OCD comments that according to tradition the kings held the first census, at some unknown date, followed by the consuls. The censorship was traditionally established in 443, at which point the censors were in charge of the census until 22, when Augustus abolished them and the emperor took over censorial powers. The powers of the censor included more than just the census, but that's not what we're interested in, your question's about the actual census. The census could be held every five years (but was not always--it could only take place if a censorial election took place, and censors were not always elected every five years. There were no censors between 70 and 28, for example, and hence no census took place during that period) and counted all citizens in the city. During a census citizens assembled in the city (at some point the cities of Italy could hold their own census at the same time as the one in Rome, so that citizens living too far from Rome to conveniently travel could register in their hometowns--it's mentioned in the tabula Heracleensis, but we don't know if it actually predates Caesar at all) and stated some stuff about who they were, what their family was, what they did for a living, and how much property they had, which the censors compiled in a list. The information was used to classify citizens in their tribes (for the purposes of organizing the tribal assemblies) and to organize them into their centuries (for the centuriate assemblies). Additionally, the listing of property meant that only during a census could you move up or down a class, so the lull in censorial elections between 70 and 28 almost certainly enabled a large portion of the senatorial class to remain in the senate, even if many of them were heavily indebted or, like Catiline, straight-up broke. We don't know much about provincial census before Augustus--Cicero in the In Verrem mentions locally-elected censors in Sicily, so they existed in that province (at least under Verres), but Sicily was kind of a funky province and was pretty seriously exploited, so we can't tell if they existed elsewhere. It seems that provincial governors were in charge of determining population figures during their terms of office--it didn't matter that much, since the census recorded citizen information for the purposes of army recruitment, electoral organization, and class structure, not for taxation. The system of tax-farmers didn't need to know how many people were in a province, since they were not originally taxed per head. Augustus organized provincial censuses overseen by the provincial governor, but I don't really do the Principate so I'm not entirely sure how those worked.