Are 'afdeling' and 'departement' interchangeable? Is one more common than the other? Is one more formal?
"Afdeling" is used most commonly. It refers to any department that is focused on one certain product. For example, the fruit department in the super market would be the "fruitafdeling".
A "departement", while meaning pretty much the same, is only used for certain very specific situations, usually business related. For example, the departments that fall under each minister (government) are called "departementen". ("He works at the department of defense") Also certain parts of countries are called this, like in France, where they don't have provinces, but rather "arrondissements" (departments).
So "afdeling" is definitely more commonly used and probably the only one you need, unless you are planning on going into politics ;)
Just to clarify. In France "arrondissements" are a separation within a city (Paris is divided into arrondissements). We also have "départements" which are like provinces (Lyon is a city in the "Rhône" department).