The difference is about the resulting SQL Query to be executed on the database... I personally prefer "__icontains" because is supported for all databases, and "__search" only for mysql (as django docs) (also supporting PostgreSQL in Django ≥ 1.10 — see documentation).
Look at the query for each method:
Using __search
>>> str(Contact.objects.filter(first_name__search='john').query)
'SELECT `contact_contact`.`id`, `contact_contact`.`title`, `contact_contact`.`first_name`, `contact_contact`.`last_name`, `contact_contact`.`user_id`, `contact_contact`.`role_id`, `contact_contact`.`organization_id`, `contact_contact`.`dob`, `contact_contact`.`email`, `contact_contact`.`notes`, `contact_contact`.`create_date` FROM `contact_contact` WHERE MATCH (`contact_contact`.`first_name`) AGAINST (john IN BOOLEAN MODE)'
Using __icontains
>>> str(Contact.objects.filter(first_name__icontains='john').query)
'SELECT `contact_contact`.`id`, `contact_contact`.`title`, `contact_contact`.`first_name`, `contact_contact`.`last_name`, `contact_contact`.`user_id`, `contact_contact`.`role_id`, `contact_contact`.`organization_id`, `contact_contact`.`dob`, `contact_contact`.`email`, `contact_contact`.`notes`, `contact_contact`.`create_date` FROM `contact_contact` WHERE `contact_contact`.`first_name` LIKE %john% '