There is no job that you can do that will specifically give you the Black headband. You've got a chance of finding an item on just about any job you work at, depending on your luck.
The easiest way to acquire it would be to buy it from a Tailor shop in a town. If you are a citizen of that town and it's an item that's for sale at the Tailor, it's only $18. However, if you're not a member of a town or need to buy it from a town you don't belong to, plan on paying $72 for it.