Should I use one-to-many or many-to-many to log previous records?
I don't think there is many-to-many relationship exists in this case as the Intern will always be associated with a single company.

I would prefer to go with say a LOG (or InternCompanyHistory) table to save InternId, CompanyId and DateOfChange or any other attributes associated with change of company.