(Yes, you can use heuristics to guess which endianness is in use. The problem is that while this is trivial for Western languages I don't even know how you'd begin when presented with arbitrary text using an East Asian or African written language.)
Not actually that hard.
Consider a document which is encoded in either a) ASCII like you know it or b) ASCII where the top 4 bits and bottom 4 bits are transposed. How would you tell the difference? Well, one can imagine creating a histogram of the bits for each half of the bytes and comparing them to expectations based on the distribution of bits in naturally occurring English text. The half with most of the entries in the 0x5, 0x6, and 0x7 is the upper order half.
If you don't know what naturally occurring e.g. Japanese looks like in Unicode code points, take this on faith: flipping the order does not give you a document which looks probably correct. (Also, crucially, Japanese with the order flipped doesn't resemble any sensible document in any language -- you end up with Unicode code points from a mishmash of unrelated pages.)
P.S. Why care about that algorithm? Here's a hypothetical: you're a forensic investigator or system administrator who, given a hard drive which has been damaged, need to extract as much information as possible from it. The BOM is very possibly not in the same undamaged sector which you are reading right now, and it may be impossible to stitch the sectors without first reading the text. How would you determine a) whether an arbitrary stream of bytes was likely a textual document, b) what the encoding was, c) what endianness it was, if appropriate, and d) what human language it was written in?
1. Try both byte orders
2. If one produces valid text and the other does not, choose that one (this will get you the correct answer almost every time, even if the source text is Chinese)
3. If both happen to produce valid text, use the one with the smallest number of scripts
(Note that this just determines byte order, while Patrick was talking about the more ambitious task of heuristically determining whether a random string of bytes is text and if so what encoding it is. My point is just that you really don't need to be told the order of the bytes in most cases.)
Try saving a text file in Windows XP Notepad with the words "Bush hid the facts" and nothing else. Close it and open the file again. WTF Chinese characters! Conspiracy!
The UTF-16 encoding scheme may or may not begin with a BOM.
However, when there is no BOM, and in the absence of a
higher-level protocol, the byte order of the UTF-16
encoding scheme is big-endian.
Another thing I noticed in the article: the encodings issue was historically even more complicated: Unicode previously only covered what is now the basic multilingual plane (BMP), which meant all code points could be encoded with a single 2-byte value, a.k.a. UCS-2. When more code points got added, that exceeded UCS-2's range, so that mutated into the variable-length UTF-16 encoding. Had Unicode been introduced into Windows and Java later, who knows if they'd ended up using UTF-16.