Choosing an internet nickname is more serious a task than one might realise. It is not quite as important as choosing your child's real name, or changing your own, but it is still worth devoting a reasonable amount of time to, because, if you end up spending as much time on the internet as I have in the last five years, then you may find yourself running up against several problems.
How can one ensure that these unfortunate things never happen - or at least, as infrequently as possible?
Different communities will have different numbers of members. Depending on this number, obvious nicknames like bubble may be available, or insanely obscure ones like stickmansam1024 - and any and all variations on your real name - may be taken. So a good place to start looking if you want to pick a nickname which is likely to be available everywhere is AOL Instant Messenger (AIM) - which, if America Online is to be believed, has over 195 million registered users. That's 195 million nicknames already taken. Hotmail is another good place to start, with over 110 million users, though picking email addresses is a little different from picking nicknames. Lastly, do a quick Google search for your prospective nickname. If your chosen name is available on both AIM and Hotmail, and returns 0 hits from Google, then you have a very good shot* at it being available everywhere on the web.
Adding random numbers to the end is, of course, cheating. ;)
* Not, of course, a guarantee; Google doesn't index everything
To make sure it will be valid everywhere, use at least eight characters. Avoid underscores, periods, hyphens, or other miscellaneous punctuation like exclamation marks which some communities allow and others don't. Ideally, stick with your standard lower-case alphabet and the ten digits. Upper-case and spaces are fine and allowed in many communities... but not email addresses. You might or might not care about this. Profanity is frowned upon in many communities and sometimes automatically disallowed.
Update: Blizzard's popular PC title "World Of Warcraft" has an extremely strict naming policy, but most of the restrictions in there are, in my opinion, for the best. You'd do well to give the list a skim, even if you don't play or plan to play WoW.
Avoid references to current events or things you like now, but are likely to change, such as bands, videogames, videogame characters, videogame consoles and sports teams. Don't put a year in unless it's your birth year, or you plan on either changing your nickname or looking foolish come 2005. Call yourself "gothchick" and you may regret it on the day you decide you're no longer a goth.
Most difficult to prepare for is the gradually building feeling - maybe two or three years down the line - that this name just doesn't suit you any more. Using a variation on your real name is your best bet to avoid this, but otherwise, this is something you really have to look deep into your soul if you want to avoid.
If you aren't too worried about having to change your name in the future, then it may help to at least have some constant element within it. A mate of mine has been using various nicknames containing the word "Wackypants" for years, and pretty much all of mine contain the string "Sam", which, in case you were wondering, is my first name.
Other questions you may wish to ask yourself about your nickname are "Is it obvious how to pronounce this?", "Does it abbreviate well?", "Am I going to have to explain this to people every time?" (for example, "that's a 1, not an l" or "there are exactly six a's in Daaaaaave"), "Is it a nightmare to type out in full?" and "Do I care?"
This is perhaps more important in terms of email addresses than anything else. If you are emailing a potential employer or elderly relative or the President or anybody else whom you'd speak to in a reasonably straight tone of voice, then making them reply to "cute_kitty2002@" or something incorporating heavy use of L33t isn't likely to generate a good impression. Using a variation your full name - I use "samdhughes@" usually - is often your best bet for serious correspondence. Of course, email can be redirected so ultimately this may not matter to you too much.
Picking a nickname in a larger community is generally a major test of imagination in any case. Certain words, phrases and numbers are INCREDIBLY popular - for example, "007" in male nicknames, "chick" in female ones, "uk" appended to any British person's nickname. Just browsing random internet message boards for any length of time will provide you with lots of highly bland, uninteresting nicknames. Check the community's advice on the subject (this is from AOL's AIM Screen Names FAQ):
Q: What can I do if the Screen Name I want is already taken?
A: If the Screen Name you want is already taken, try variations of that name, or select another. You can use up to 16 letters, numbers, and spaces for your Screen Name. For example, if the Screen Name you want is "joebloggs", try using "joebloggs1," "joebloggsuk," etc.
...for a perfect example of what you should NOT do if you wish to stand out from the crowd at all. If you're joining a community oriented towards a certain subject, such as, I dunno, Perfect Dark, don't pick a nickname that is either "[something] Dark" or "Perfect [something]", and especially not "perfectdarkness1287".
If you want to stay close to home, try a variation on your real name or a coagulation of your name and something you consider really cool. Take a little-known reference from fiction. Neal Stephenson's book Snow Crash contains a user who calls himself "da5id" - 5 being represented by V in Roman numerals, you see - which is a cool nickname, if 1) usually too short, and 2) by virtue of originating in an extremely popular book, almost certainly already taken in any reasonably large community. Wintermute is an AI from William Gibson's book Neuromancer, but again, you'll usually find yourself needing to go for something more obscure. Find something you love and honour it. Shakespeare references are cool, classic 1970s British children's television references are cool, geeky references are cool if you are indeed a geek - but please, make them sufficiently geeky. Calling yourself "Neo" does not count. Choose lengthy and little-known self-descriptive words from a thesaurus. Name yourself after an obscure figure of Norse mythology who resonates with your personality, or the Latin name for a groovy species of fish.
My personally recommended method - because all of these methods are fallible, depending as they do on information that everyone else also has access to - is to simply make up a word which means nothing but sounds cool. Google for it to make sure it doesn't mean anything in another language. A friend of mine tends to call himself "Ardeninian" when he's playing Quake. This is a great nickname in my opinion - ten characters long, meaningless, pronounceable, 0 Google hits except for himself, it's all one word, no numbers, no punctuation, wholly original, wholly respectable.
Finally, forget everything I've just told you, and every screen name you've ever seen, and just MAKE IT UP YOURSELF.