When adding a new contact for a company, how do I add a different DEPARTMENT or DIVISION for the contact? Right now when I add a contact the fields are greyed out.

You can't, those fields are for company records only. If you need to record that information create some contact specific User Defined Fields, enter the information there.