You could also do this using subqueries.
Get all departments. The 'of' relationship is the inverse of company to-many departments:
-(void)printDepartmentsWithSalaryHigherThan:(int)salary inContext:(NSManagedObjectContext *)context {    
    NSFetchRequest *request = [[NSFetchRequest alloc ]init];
    request.entity = [NSEntityDescription entityForName:@"Department" inManagedObjectContext:context];
    request.predicate = [NSPredicate predicateWithFormat:@"SUBQUERY(employees, $emp, $emp.salary > %@ ).@count > 0", [NSNumber numberWithInt:salary]];
    for(Department *dep in [context executeFetchRequest:request error:nil]){
        NSLog(@"Department: %@", dep.depName);
        NSLog(@"in Company: %@", dep.of.compName);
    }
    [request release];
}
Or, if you have more companies and just want the companies that have an employee with a salary 'higher than' some amount. A subquery based on the result of a subquery
-(void)printCompaniesWithHigherSalaryThan:(int)salary inContext:(NSManagedObjectContext *)context {
    NSFetchRequest *request = [[NSFetchRequest alloc ]init];
    request.entity = [NSEntityDescription entityForName:@"Company" inManagedObjectContext:context];
    request.predicate = [NSPredicate predicateWithFormat:@"SUBQUERY(departments, $dep, SUBQUERY($dep.employees,$emp,$emp.salary > %@).@count > 0 ).@count > 0", [NSNumber numberWithInt:salary]];
    for(Company *c in [context executeFetchRequest:request error:nil]){
        NSLog(@"Company: %@", c.compName);
    }
    [request release];
}