Perfect, that did exactly what I wanted it to.
Below is what I finally used:
internal static PatientCollection SearchMyPatients(string searchText)
{
searchText = String.Format("%{0}%", searchText);
EntityField concatenatedExpression = PatientFields.FirstName;
concatenatedExpression.ExpressionToApply = new DbFunctionCall("{0} + ' ' + {1}", new object[] { PatientFields.FirstName, PatientFields.LastName});
PredicateExpression predicate = new PredicateExpression();
predicate.Add(PatientFields.DoctorId == SessionManager.CurrentDoctorId);
predicate.AddWithAnd(PatientFields.FirstName % searchText | PatientFields.LastName % searchText | concatenatedExpression % searchText);
SortExpression sort = new SortExpression();
sort.Add(PatientFields.LastName | SortOperator.Ascending);
return GetPatients(predicate, sort);
}