Federal Filing Status. "Exempt from Withholding" can only be claimed if you paid no tax last year and you don't expect to pay any this year too. In most cases, this is not going to happen.
Federal Withholding Allowance. Calculate this based on what you enter into the W4 form.
Essentially, the government is giving you the chance to a deduction on your taxable income (this is a "tax break"). You can take the standard deduction which is pretty much based on whether you're single or married (~$6,300), or if you think you can go through the specifics and come up with more than the amount you would get from just the standard deduction, you can do that (but you'll have to be able to prove it). With the standard, you don't seem to have to prove it, it's just free. Common ways you could actually have deductions greater than the standard is if you paid a lot of student loan interest, or interest on your mortgage. If you can come up with a number greater than the standard deductions, you can use that to get more off. Otherwise, you should just use the standard.
State and local taxes are deductible. It seems like a $110k salary is $7,100 in state income taxes, which is greater than the $6,350 you get from the standard deduction. Therefore, if you have a high paying salary and a state with high income taxes, it might make more sense to itemize.
You also have to do the same kind of form for your state. In California, it's the DE-4. You calculate the same thing, "withholding allowances", based on whether you're single, married, etc. You can't rely on the number being the same, even though it often is. In California, it seems to be different than what the W-4 calculates. Also, the California DE-4 form makes it very clear that you can't just use the same number.
If at any point your situation changes and more needs to be withheld, then you are obligated to submit an update (probably to your employer, since they're doing the withholding).
If you have multiple jobs, do not claim the allowances on both jobs, just do it on one (usually the highest paying one) and do zero on all the others. Otherwise you might be getting under-withheld.
Head of household: you can put 1 if you are paying for the majority of your home and you have at least one dependent (could even be a parent who you are paying for, or someone who lives in your house for more than half the year).
Note: it seems you can reduce your taxable income by up to $2500 if you spent that much on interest on your student loans.