R with the standard (total) order and the functions min and max corresponding to that order form a lattice (in the sense of universal algebra). Also, given the functions min and max, the order on R can be recovered. The square RxR of this algebra gives another lattice whose associated (partial) order is your $R^2$. You can generalize the construction above: if f,g, and h are increasing functions on certain ranges, and B is a binary function which preserves the order on the right part of RxR, then so will f(B(g(a),h(b)) preserve the order. (Essentially f has to capture the range of B, which has to capture the range of g and h in a certain way.) So you can replace + by min and other order-preserving operations.
I do not know, but I do believe, that the above construction does not capture all operations if you limit B to range over a finite set of binary operations. I am confident, however, that a practicing order theorist or universal algebraist can give you a better, if not decisive, answer. If you want to do some more research, consider clone theory and sets of operations which preserve a given relation.
To the contrary, there is also a memory of a result of Kolmogorov which is something like every continuous function over R in some number (three) of variables can be rewritten using just addition and functions of one variable. There may be other conditions on this result which relate to your question.
(To partially counter Mark Sapir's opinion, I offer a result of Kolmogorov and Arnold. Forgive the lack of accents. Every continuous function (on the reals) in three variables can be written as a sum of 6 unary functions, each of which has as arguments a sum of three other unary functions, one for each of the three variables. This suggests that any continuous order preserving function of two variables can be written with a term composed of at most 17 addition operations and at most 24 unary functions. One can probably do better, but at least it suggests that many order-preserving binary functions are not too far removed from addition. If it can be shown that every binary order-preserving functions is of the form f(B(-,-)), where B is continuous and order preserving, then you will have all such operations generated by addition and unary functions, contrary to my belief above that you need infinitely many such binary operations.)
Gerhard "Ask Me About System Design" Paseman, 2010.12.15