When trying to run the following code:
    Expression<Func<string, string>> stringExpression = Expression.Lambda<Func<string, string>>(
        Expression.Add(
            stringParam,
            Expression.Constant("A")
        ),
        new List<ParameterExpression>() { stringParam }
    );
    string AB = stringExpression.Compile()("B");
I get the error referenced in the title: "The binary operator Add is not defined for the types 'System.String' and 'System.String'." Is that really the case? Obviously in C# it works. Is doing string s = "A" + "B" in C# special syntactic sugar that the expression compiler doesn't have access to?
It's absolutely right, yes. There is no such operator - the C# compiler converts string + string into a call to string.Concat. (This is important, because it means that x + y + z can be converted into string.Concat(x, y, z) which avoids creating intermediate strings pointlessly.
Have a look at the docs for string operators - only == and != are defined by the framework.
This just caught me out too, and as Jon points out in his answer, the C# compiler converts string + string into string.Concat. There is an overload of the Expression.Add method that allows you to specify the "add" method to use. 
var concatMethod = typeof(string).GetMethod("Concat", new[] { typeof(string), typeof(string) }); 
var addExpr = Expression.Add(Expression.Constant("hello "),Expression.Constant("world"), concatMethod);
You might want to change the string.Concat method to use the correct overload.
Proving this works:
Console.WriteLine(Expression.Lambda<Func<string>>(addExpr).Compile()());
Will output:
hello world
Yeah, it's a surprise isn't it!!! The compiler replaces it with a call to String.Concat.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With