So my anecdotal evidence is it's in order of the character's addition to the realm, whether by creation or transfer.
That's been my experience as well, so I'd put in my vote for GUIDs and played time being irrelevant for character selection screen ordering. It would be nice to have some way to manually sort them, though... my main character is #7, my main alt is #3, my original main which I don't play anymore is #1, and my level 49 bank alt is #2. :|
My characters are not in the order I created them. My first created character shows up as 4th, my second as 3rd, my third as 5th...
My last two created characters do show as last two entries in the list, everything else is clearly out of order.
That's the very reason why there are theories like it may be the GUID, because if it's creation date on realm it's obvious when it works that way. It simply doesn't. Say it is GUID, that still allows for some people to have their characters show in creation order as roughly GUIDs do increase with increasing population...
I don't have time right now to log into all my characters, but in order of first three on login screen they are indeed ordered per GUID checking with a simple /print UnitGUID("player"), and as said that's not their order of creation.
That doesn't prove that it's GUID but it's certainly a better candidate than creation time because that's just plain false for my login screen. But it does prove that later created characters can get a lower GUID than earlier created ones, which does hint at GUID reuse unless blizz intentionally garbles, skips or randomizes GUIDs which is very unlikely.
I think that, at least in EU realms, the player database was rebuilt once.
I remember the day my characters changed ordering. Before that, they were sorted by creation order, that changed that day and never since. Characters created after that were put after, and in creation order. So the ordering changed only once, for me.
The character selection screen and the information printed with '/chatinfo [channelname/channelnumber]' are sorted by GUID!
A new character GUID is created if you create a character or if you transfer your character to another realm.
A GUID indicates how recently a character was created on a realm.
A GUID is definitly unique in a battlegroup. It must be unique for _all_ eg. european realms too (Blizzard is testing cross-language battlegrounds on european servers!)
A GUID is never reused! If you delete a character NO newly created character will ever get that GUID.
I collected GUIDs from 63 german and english EU realms (mainly through battlegrounds) and I must say, I never saw the same GUID twice (I checked that for the top 1000 GUIDs of that 63 realms [currently ~25000 GUIDs]). Sure, nobody can track all GUIDs, but believe it or not, I bet a GUID exists only once for a whole region or a whole data center (eg. Europe / US / and so on).
(Don't ask why I collect GUIDs...I just wanted to know who has an old char and who not... that's why I created GT100GCX - Gnomish Top100 GUID Catcher Xtrem - http://www.wowace.com/projects/gt100gcx/ ... yep it's useless - and yes the battlegroup selection is useless, because of what I wrote here. this needs some update in this addon...)
If you look at the GUID list of different realms you can see, that each realm has a reserved GUID range that starts at a specific GUID and go upwards until this range is reached.
Each realm has such reserved GUID ranges.
If this reserved GUID range is reached the next GUID starts at a new reserved GUID range.
The reserved GUID range depends on when a realm is established. eg. the first character GUID of a new open realm has the highest GUID (depends on other realms population, but my empiric experience says that the reserved GUID ranges are very very high and you can only see 'reserved GUID ranges' if you track large numbers of GUIDs on different realms with different age).