Class with TryParse static method

The TryParse or TryGetValue pattern is often used in the .NET Class Library and is a good approach. In order to fully comply with it, you should always return the type's default value for the output parameter (default(T)) when the parsing fails. For reference types this is always null:

public static bool TryParse(string expression, out OrderExpression orderExpression) {
    if (_parser.ExpressionIsValid(expression)) {
        orderExpression = new OrderExpression { Rules = _parser.Parse(expression) };
        return true;
    } else {
        orderExpression = null;
        return false;
    }
}

An out parameter must be assigned before leaving the method anyway. You'll get a compiler error otherwise.

Also, in C#, the C# type aliases are usually preferred over the .NET type names. I.e.: use string instead of System.String, bool instead of System.Boolean, int instead of System.Int32 and so on. (Personally, I prefer to use the .NET type name when accessing static members: Int32.TryPare(...).)

When calling a method, the return value can be ignored in C#, but here, it seems logical to react differently, depending on the outcome of the parsing:

if(OrderExpression.TryParse(expression, out orderExpression)) {
    // Use orderExpression.
} else {
    // Handle the error case.
}

A comment regarding the logic: Order expressions usually have to be executed in a specific order, however, a HashSet<T> is unordered. Shouldn't the parsing return a List<OrderExpression> instead?

If the list of rules should be immutable after parsing, consider to remove the setter of the Rules property and use ReadOnlyCollection instead of the HashSet:

public class OrderExpression
{
    private (IEnumerable<OrderRule> rules) {
        _rules.AddRange((rules ?? Enumerable.Empty<OrderRule>());
    }
    private readonly List<OrderRule> _rules = new List<OrderRule>();        
    public ReadOnlyCollection<OrderRule> Rules { get { return _rules.AsReadOnly(); } }

    public static Boolean TryParse(string expression, out OrderExpression orderExpression) {
        // Parse expression into a List<OrderRule>
        if (_parser.ExpressionIsValid(expression)) {
            orderExpression = new OrderExpression(_parser.Parse(expression))
            return true;
        }
        else {
            orderExpression = default(OrderExpression);
            return false;
        }
    }
}

Parsing the expression shouldn't a part of the OrderExpression. You should create another class that does nothing else but parsing. You might want to add some options to it later or unit-test it so it's better if the OrderExpression doesn't have to care about things that are not order-expression related (like the potential parser options etc.)

public class OrderExpressionParser
{
    public OrderExpression ParseOrderExpression(string value)
    {
        // parse the order expression....       
        return new OrderExpression(...);
    }
}

This way you can test the parser independantly and exchange it later without modifying the OrderExpression class that can remain as simple as:

public class OrderExpression
{
    public OrderExpression(List<OrderRule> orderRules) { ... }

    public IReadOnlyList<OrderRule> OrderRules { get; }
}

Then you would write:

var orderExpressionParser = new OrderExpressionParser();
var orderExpression = orderExpressionParser.ParseOrderExpression("+foo;-baz");

if (orderExpression == null)
{
    return;
}

 // do something...

If you however prefer the TryParse approach I'd add the parser as a static property to the OrderExpression:

public class OrderExpression
{
    public static OrderExpressionParser OrderExpressionParser { get; set; } 
        = new OrderExpressionParser();

    public OrderExpression(List<OrderRule> orderRules) { ... }

    public IReadOnlyList<OrderRule> OrderRules { get; }

    public static bool TryParse(string value, out OrderExpression result) =>
        (result = OrderExpressionParser.ParseOrderExpression(value)) != null;

IMHO, static TryParse method only makes sense for value types, when its impossible to mutate an existing instance and/or its hard to tell the difference between default(T) and successfully parsed value. For all other situations a constructor (for immutable types) or an instance method (for mutable types) will do a better job at keeping your code clean.

I am OK with this (for immutable objects):

// you can throw exception if string should be valid, but it is not
var expression = new OrderExpression(str);

Or this (for mutable objects which need to be updated):

var expression = new OrderExpression();
expression.TryParse(str);
//or 
//expression.TryUpdate(str);

Or this (good approach in general):

//for invalid strings: return null or throw
OrderExpression expression = _parser.Parse(str);

But using static method in your case does not feel right to me.