I registered mine with Vidahost (use code "edent" for a discount!) - but your current host or registrar should be able to register one for you.

You are limited in the characters you can have - and some domains are more forgiving than others. For example, Dan Lane uses ☎.tk (that's the telephone symbol).

Generally speaking, you can't mix languages - so you can't have Russian and Japanese in the same domain.

I use Verisign to validate my Punycode, but other services are available.

Finally, some registrars have very strict registration rules. I wasn't able to register a .中国 (Chinese) domain because I couldn't prove I had the rights to the trademark for "Shakespeare".