The search fields will contain a combination of the row identifier and the value of the displayed column, divided :#, in your case, which may be 1:#HumanResourcesor 12:#Engineering.
, , . , SharePoint SPFieldLookupValue, :
var department = web.Lists["Department"].GetItemById(1);
var employee = web.Lists["Employee"].Items.Add();
employee["Name"] = account.Name;
employee["Department"] = new SPFieldLookupValue(department.ID, department.Title);
employee.Update();