SCA names usually consist of two parts: the given name and the byname(s). The given name is what your parents would have given you at birth, and the byname would be used to distinguish you from all others who share your given name.

Bynames were usually short, direct, and easy to remember; after all, they were used every day. Some examples of bynames are: occupational names, such as Tanner, or Smith; patronymics, or names showing descent, such as ap Morgan, Ivanov, or ibn Yusuf; names derived from where you lived, such as von Faulkenstein, or Fleming; epithets, or descriptive names, such as the Temperate, or Dubh (black-haired); and names expressing something symbolic about you, such as an action (Shakespeare), a favorite oath (Godesgrace), or a badge (de la Rose). Over time, these categories have tended to overlap; and some of these names lost their original meanings and came to be hereditary surnames.

1) Don’t claim to be someone or something you’re not;

2) Don’t do something they wouldn’t have done in medieval times

To be specific:
1) Your name shouldn’t be too similar to that of a historical personage, or of a character in fiction, or of another SCA member. You can be Robert, but not Robert the Bruce or Robert d'Ammonville  (both of which are taken). For that matter, you should avoid close kinship to protected names: calling yourself Robert McConan the Barbarian, for instance, would be a direct claim.
Don’t try to claim non-human descent. Everyone in the SCA is human.

2) Try not to have elements from too many cultures in your name. e.g.; Fransois vonDrakken apDonnell is inappropriate. Names used only one language, or sometimes two. Most people didn't travel far from home, and knew just the one language they grew up with. As a result, names with two languages appeared only near kingdom or national borders, or as a result of regular trade or invasions. Thus, it's reasonable to combine English and Irish, or German and Swiss, because those people ran into each other regularly. On the other hand, mixing Arabic and Irish, or Hungarian and Chinese, isn't reasonable, because those people rarely interacted, if at all.

The given name you choose should have been used as a given name in  SCA period (before AD 1600, but name documentation is accecptable up to 1650).Even though many given names were taken from common words, not all common words were used as names. Using surnames as given names, while common today, wasn’t usually done in period. In most cases, you can use one of your legal given names, whether it is medieval or modern (be prepared to provide a copy of your birth certificate, though).

In the SCA, females sometimes use male names, and vice versa; but you might wish to think twice before deciding to do so. Certainly, you shouldn’t use male and female elements in the same name (e.g. Tiffany Thorvaldson).

And, finally,  be kind to all your new friends and choose a name that’s not too hard to spell or pronounce!

To start with, you may want to consider just what nationality your new persona will be. If it’s to be German, for instance, you’ll want a basically German name. This is your chance to be the character you’ve always wanted to be: Norse lord, Bregundian lady, German merchant, Swiss mercenary...

If you want to think carefully about your new name for awhile, yet still play in the SCA, a simple solution would be to continue to use your modern given name, with the name of your local branch as a byname; for example, William of Silver Desert.

You will probably want to avoid the supermarket "Name Your Baby" books. They’re geared to a modern audience, and are frequently inaccurate; many of the names are unsuitable for SCA use. Instead, look up Heini Gruffudd's Welsh Personal Names or E.G. Withycombe's Oxford Dictionary of Christian Names to get a feel for medieval names.

Finally you should talk with your local heralds for further references and advice.

(Note: This document was built from various sources and slightly modified to make it more applicable to the West Kingdom.)