What's a non-abelian totally ordered group? Because I have heard the phrase "totally ordered abelian group", I imagine there should be non-abelian ones.  By this I mean a group with a total ordering (not to be confused with a well-ordering) which is "bi-translation invariant": a < b should imply cad < cbd.
Does anyone know any examples?  
Totally ordered abelian groups are easy to come up with: any direct product of subgroups of the reals, with the lexicographic ordering, will do.  Knowing some non-abelian ones would help reveal what aspects of totally ordered abelian groups really depend on them being abelian...
Edit: Via Andy Putman's answer below, I found this great summary of results about ordered and bi-ordered groups (i.e. groups with bi-translation invariant orderings) on Dale Rolfsen's site:
Lecture notes on Ordered Groups and Topology
He shows numerous examples of non-abelian bi-orderable groups, including a bi-ordering (bi-translation invariant ordering) on the free group with two generators.  As well, he mentions, due to Rhemtulla, that a left-orderable group is abelian iff every left-ordering is a bi-ordering, which I think really highlights the relationship between ordering and abelianity.
 A: What you want is to define a positive subset of the group that satisfies trichotomy (every group element is either positive, negative, or the identity), that is closed under the group law, and that is invariant under conjugation.
I think that the Heisenberg group is an example.  This is the group of matrices M = [[1,a,c],[0,1,b],[0,0,1]].  Say, integer matrices.  Then we can say that M is positive if a > 0, or if a = 0 and b > 0, or if a = b = 0 and c > 0.  I think that this works?
A: Thurston's construction of a left-order on braid groups uses hyperbolic geometry, but it doesn't have to. For the sake of argument, let S be a closed, oriented surface of non-positive Euler characteristic. The universal cover of S is homeomorphic to the plane. An essential embedded loop in S lifts to a properly embedded line in the plane. The mapping class group of S permutes the set of isotopy classes of essential embedded loops in S, and a certain extension of this group acts on the universal cover, permuting the set of embedded lines covering properly embedded curves on the surface. Any collection of proper embedded rays in the plane whose pairwise intersections are compact inherits a natural circular order from the topology of the plane; it is this circular order that gives rise to circular orders on (certain extensions of) mapping class groups, and left orders on braid groups.
A: Thompson's group $F$ is totally ordered.  See here for a description of all possible bi-orderings.  Indeed, all diagram groups are totally orderable (see here).  The pure braided Thompson group $BF$ also bi-orderable (see here).
A: This concept is usually called biorderability (there is also left- and right-orderability).  There are many examples, such as free groups and surface groups.  Most spectacularly, the pure braid groups are biorderable, while the full braid groups are left orderable but not biorderable.  The left ordering on the braid groups is usually attributed to Dehornoy, though it was discovered even earlier by Thurston (but not published).
Dale Rolfsen has several nice surveys of material related to this on his webpage here.  In particular, there is the complete text of a nice book called "Why are braids orderable?" that he wrote with Patrick Dehornoy, Ivan Dynnikov, and Bert Wiest.  I believe that a new and much expanded edition of this book was just published.
EDIT 1 : I just found the website for the much-expanded version of Rolfsen et al's book here.
EDIT 2 : Thurston's construction of a left-ordering on the braid groups (which, of course, uses hyperbolic geometry) is very beautiful.  It is explained very nicely in the first few pages of the paper "Orderings of mapping class groups after Thurston" by Short and Wiest, which is available on the arXiv here.  The intro sections of this paper also contain a brief but enlightening account of the general theory of group orderings.
Also, I have not read it, but there is a book entitled "Orderable Groups" by Rehmtulla and Mura.  However, it is from 1977 and will thus omit a lot of recent work.
A: The following should be a comment, but it's too long, and it does contain an answer in passing.  I heard the following story from Andrew Glass.  Saharon Shelah arrived in Vancouver, at a time when several ordered-group theorists were there, including Charles Holland and Alan Mekler.  The following conversation took place (SS = Saharon Shelah; OGT = ordered-group theorists):
SS: Do you have any interesting problems?
OGT: Yes, is there a linear order that is the underlying order of an ordered group but not of any ordered abelian group.
SS (after a moment's thought): Are there any non-abelian ordered groups?
OGT: Yes, free groups can be ordered.
SS: Oh; how do you do that?
OGT show him how to linearly order free groups.
SS (without further time for thought): Oh.  Then here's the answer to your question. ...
Shelah's answer at that point used the a set-theoretic principle known to be consistent but independent of ZFC (diamond, if I remember correctly), but that assumption was later eliminated in joint work.  See "Lawless Order" by Holland, Mekler, and Shelah [Order 5 (1985) pp. 383-397].
A: Not really an example (see the edit below), but somehow related to Greg Kuperberg's one: Let $\mathbb A = (A, +, \cdot, \preceq)$ be a strictly totally orderable semiring (*) and for a fixed integer $n \ge 1$ let $\mathcal M_n(A)$ denote the set of all $n$-by-$n$ matrices with entries in $A$, endowed with the usual operations of addition, say $+$, and row-by-column multiplication, say $\cdot$, induced by $\mathbb A$. Then, $(\mathcal M_n(A), +, \cdot)$ is itself a semiring. So now, let ${\rm U}_n(\mathbb A^+)$ (respectively, ${\rm L}_n(\mathbb A^+)$) be the subsemigroup of $(\mathcal M_n(A), \cdot)$ consisting of all and the only upper (respectively, lower) triangular matrices whose entries on and above (respectively, below) the main diagonal are positive in $\mathbb A$. Then, both $({\rm U}_n(\mathbb A^+), \cdot)$ and $({\rm L}_n(\mathbb A^+), \cdot)$ are strictly totally orderable semigroups.
Edit. Sorry, I've just realized that the question was focused on groups, and not on semigroups/monoids! But then let me profit from my lack of attention to turn the above into a question: Do $({\rm U}_n(\mathbb A^+), \cdot)$ and $({\rm L}_n(\mathbb A^+), \cdot)$ embed into strictly totally ordered groups in the case when $(A, +, \cdot)$ is unital and commutative?
(*) Here, a semiring is just a (possibly non-unital or non-commutative) ring whose additive monoid is not necessarily a group. A strictly totally ordered semiring is then a $4$-uple $(A, +, \cdot, \preceq)$ such that $(A, +, \cdot)$ is a semiring and $\preceq$ is a total order on $A$ such that 


*

* $(A, +, \preceq)$ is a strictly totally ordered magma (in fact, a monoid), namely $x + z \prec y + z$ and $z + x \prec z + y$ for all $x,y,z \in A$ with $x \prec y$.

* $x \cdot z \prec y \cdot z$ and $z \cdot x \prec z \cdot y$ for all $x,y,z \in A$ with $x \prec y$ and $0 \prec z$, where $0$ stands for the identity of the monoid $(A,+)$. 

A: As the OP was aking for examples, here is a very simple and elementary way to define a total ( bi-invariant ) ordering on the free group using the Magnus transformation which, an alphabet
$X=\{x_1,\cdots ,x_n\}$ being given, sends a reduced ( and, in fact, any ) word
$g=x_{i_1}^{\epsilon_1}x_{i_2}^{\epsilon_2}\cdots x_{i_k}^{\epsilon_k}
\in \Gamma(X)$ ( with $\epsilon_i\in \{-1,1\}$ ) to the series
$$
S=S(x_{i_1}^{\epsilon_1}x_{i_2}^{\epsilon_2}\cdots x_{i_k}^{\epsilon_k})=(1+x_{i_1})^{\epsilon_1}(1+x_{i_2})^{\epsilon_2}\cdots (1+x_{i_k})^{\epsilon_k}\in \mathbb{Z}<<X>>
$$
( it can be shown to be injective ). Then ( if $x_{i_1}^{\epsilon_1}x_{i_2}^{\epsilon_2}\cdots x_{i_k}^{\epsilon_k}\not=1$ ), develop it as
$$
(1+x_{i_1})^{\epsilon_1}(1+x_{i_2})^{\epsilon_2}\cdots (1+x_{i_k})^{\epsilon_k}=1+\cdots + \mathbf{\lambda_w\,w} +\cdots 
$$
where $w\in X^{*}$ is the smallest word ( for some lexicographic ordering given by a total ordering e.g. by $x_1<\cdots <x_n$ on $X$ ) among words of smallest length in the support of $S$.
Then, if $\lambda_w\in \mathbb{N}_{\geq 1}$, say that $g$ is positive. In this way, one defines a "strictly positive cone" $P\subset \Gamma(X)$ and checks that it satisfies the three conditions ( for all $g\in \Gamma(X)$ )
$$
P.P\subset P\ ;\ gPg^{-1}\subset P \ ;\ P\cap P^{-1}=\emptyset\ ;\ P\cup P^{-1}=\Gamma(X)
\setminus \{1\}
$$
hence defining a strict total ordering on $\Gamma(X)$. This construction works mutatis mutandis when $X$ is an infinite alphabet.
