Самый простой путь, но довольно неправильный - добавить в справочник департаментов и сотрудников поле даты по которую активна данная запись. И в запросах всюду добавить проверку на эту дату.

Можно добавить два поля - дата с какой запись активна, и дата по какую запись активна. Тогда запросы на выборку будут еще проще - нужная дата в промежутке этих дат (BETWEEN). Чуть усложнится добавление записей, так как надо будет модифицировать конечную дату у имеющейся записи и ставить начальнкую дату у добавляемой записи больше предыдущей конечной, но это не слишком сложно.
В этому случае, если фамилия или название департамента поменялось - у текущей записи ставите конечную дату, а новую запись заводите с новой датой и измененными реквизитами.

Но возникает вопрос с ID сотрудников и депратаментов. Если они у вас определены как уникальные ключи, и нужно иметь возможность получить по сотруднику полную выборку по его одному ID, то тогда имеет смысл вынести все изменяемые реквизиты в отдельные таблицы, и уже там делать хранение по времени.

То есть в сотруднике у вас будет только неизменяемая информация, например ID, а уже фамилия, имя и отчество - хранится в отдельной таблице, с дополнительными полями дат. Запросы усложнятся к таблице сотрудников усложнять на лишний join, но зато можно будет вводить планируемые переименования, будущей датой. Ну и, опять же, для запросов на текущую дату, к примеру, можно предопределенные view использовать.