Best practice for new user attributes like department?

I use the custom profile fields for things just like that - agency, department etc.

I would recommend you to list users in groups with these properties rather than saving them as custom properties because there are many advantages with groups.
Say if you want to pick users of a particular department in particular region/cost center for task assignment
then if you are having both of them as custom properties you need to search for match within list of almost all users. In the other case you just need get intersection of users in region_group and department_group.
Not just this, groups will allow you to add user into multiple departments/roles where as custom properties you always need to have one value for costum properties.
Also Say when one user is moved to other region then moving them in groups will automatically manage their pending tasks and any reassignment is not required.

We do a combination of what is mentioned above, customFields are used for department, division, job code, employee ID, etc - then groups are created with rules for matching customField to certain values, automatically populating the groups.

@csteward: I like your idea, csteward! I'll have to read the documents on how to use groups then, especially how to deploy them.
Thank you all