What should be the valid characters in usernames?

A well-designed system doesn't necessarily need to prevent any special characters in usernames.

That said, the reason underscores have traditionally been accepted, is that underscore is typically treated as a "word" character, along with letters and numbers. It is usually the only other character given this distinction. This is true in regular expressions, and even at a base level in most operating systems (type an underscore in a word and double click the letters. The selection will extend past the underscore. Now try the same with a dash, it most likely will not.)

When not specified I use this:

(updated regex to fix the backtracking @abney317 mentioned)

^\w(?:\w|[.-](?=\w)){3,31}$

(original regex)

^\w(?:\w*(?:[.-]\w+)?)*(?<=^.{4,32})$

This requires a length of 4 with maximum 32 characters. It must start with a word character and can have non continuous dots and dashes. The only reason I use this is because it's strict enough to integrate with almost anything :)

Valid :

test.tost

Invalid :

test..tost

I don't like the readability argument when it interferes with the ability for people to use their native language in usernames.

I recommend you experiment with using character classes that incorporate http://msdn.microsoft.com/en-us/library/20bw873z.aspx#SupportedUnicodeGeneralCategories or http://msdn.microsoft.com/en-us/library/20bw873z.aspx#SupportedNamedBlocks. I haven't tried this, but

[\p{L}\p{N}\p{M}]

might be worth an experiment.

Because it allows multiple words to be represented in a somewhat readable manner.

Peronally I really, really wish folks would expand things a bit to allow dashes and apostrophes. This would allow people to use non-english phonetic names (eg: Native American tribal names like She-Ki and Ke`Xthsa-Tse)

The main reason websites enforce such rules is readability (because usernames like ~-|this<>one|-~ are annoying). It might also be because it's less work (underscores get matched by a \w+ regex, while dashes and other special characters don't), but I doubt that's a major reason.

There is no "standard", so if neither of the above reasons bother you, do whatever you'd like. Personally I'd like to see more websites accept dashes and periods, but it's really a personal preference of readability and consistency vs expression.

Depends how your usernames are used. There isn't a general rule, without knowing the context.

Underscore was traditionally allowed in identifiers in most programming languages, and was generally the only "special" character allowed.
But many web login still do not accept ANY special character and are limited to lower/upper case characters and digits...
And other are fine with really special ones ;-)

People may want to write their usernames like_this rather than likethis or LikeThis.