Is LINQ extension method Where guaranteed to preserve order?

For Linq to Objects / IEnumerable this is true - order will be maintained - for IQueryable providers it depends on the provider, many providers do not maintain order.

It looks like this fact (maintaining order) is not documented on MSDN though, so I would consider it an implementation detail that - although unlikely - might change in the future.

The Enumerable.Where extension method will, but the Queryable.Where extension method won't.

Enumerable.Where has to preserve the order, since it streams the results and there is no cache (and no logic in caching results).

Queryable.Where, on the other hand, translates the given call to something the underlying data source will understand and there is no guarantee about the ordering what so ever. This effect can be observed easily when working with relational databases. The addition of a where clause can let the database pick another index, which can change the ordering of the results. Without an explicit order by clause, the selected index will typically determine the ordering of the results.