What's a non-abelian totally ordered group?

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.

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].

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?