See naming conventions for some thoughts on how a name might be allocated.
In many traditions names have a power all of their own - for example knowing someone's true name can make it much easier to work magic on them - and we should recall that when The Creator placed Adam in authority over the rest of Creation, part of assuming the stewardship was the giving of names to everything else. The ability of names to exert control is particularly evident with spirits, who being much less anchored in solid matter than mundane beings are far more susceptible to being manipulated at a symbolic level1.
Besides a "true name" a person may have a variety of other names - these may be assumed ("call me Ishmael") or awarded (as when P. Cornelius Scipio was awarded the name "Africanus" following his victories in the Second Punic War). In some cultures an awarded name is a thing of great reverence and awarded after significant deliberation by wise men, usually to mark a rite of passage … in others the name attaches itself almost by accident (witness Privates "Pile", "Joker" and "Snowball" in Full Metal Jacket). Gaining a new name can mean a new stage in ones life (as in Genesis when Abram and Sarai are awarded their more familiar names of Abraham and Sarah or Jacob is given the name Israel).
All names mean something - and depending on the circumstances of naming the meaning may be more or less appropriate to the wearer. For a thing the name is usually descriptive in one way or the other, for people this can be much less so.
Traditionally a person's first name is given to them by one or more of their parents (or by the head of the family if that happens to be a different person) - this may occur at birth, after a naming ceremony soon after or, in the case of some groups with a high infant mortality rate, only after several years.
The name may be chosen according to divination or some social code based on the names of relatives or may just be whatever name seemed appropriate to the namer; perhaps embodying their hopes for the child as much as anything concrete. Other names, besides their given name may accrete later - in some societies, where social groups are fairly small one name may be all you need, whilst in more mobile or urban societies you may need several to achieve a unique identity. The first, most common addition is a "family name", based on the method by which your culture traced heredity - this may be a simple recitation of your ancestory ("I am Ralf, son of Hengist, son of Dolf … etc. …") or a less flexible name that identifies you as belonging to a specific kinship group.
Which names - or forms of a name - someone uses to address you can often say a lot about the relationship between you. In many societies use of the individual's given name is familiar and limited to friends and relatives - or may be a superior addressing a subordinate. Strangers and those of higher status may well be addressed by a different style (e.g. "I may well be William to him - it's Mr. Smith to you!"). Of course, there are levels to all these things - the aforementioned Mr Smith may well be "Bill" to some people but the use of a diminutive ("Billy" for example) will probably be restricted to his intimates: probably his spouse, parent and other close relatives.
Many names are culturally bound and will be remarked upon if they appear out of context - for example, attached to an individual who doesn't appear to belong to the source culture - and some may even be amusing or offensive to other cultures2. A name may also say quite a lot about the wearer's religion, caste and status - very often people who consciously abandon one culture for another will change a culturally bound name as part of the process3.
As already implied, some names - especially those gained in adulthood - can be as much titles as names, which can provide additional confusion once they've jumped a couple of language barriers. The most obvious example of this would be the names of God in most monotheistic or monolatrous religions, viz Ahrua Mazda ("the Wise Spirit" - Zoroastrianism), Allah ("He who Is" - Islam), Yaweh ("I am who I am" - Judaism/Christianity), Adonai ("Lord" - Judaism/Christianity), Ha'shem ("The Name" - Judaism), Christ ("The Annointed One" - Christianity). However, various other examples can be found in more mundane settings - it's not unknown for early anthropologists to record whole dynasties of historical monarchs with a personal name that turns out to simply be an archaic word for "king".
Another superstition related to names is that "naming calls" - to speak the name of something or someone has a chance of attracting their attention. When those entities which might be named are powerful and or dangerous then euphamisms like "the Fair Folk", "the Kindly Ones" and "Old Nick" might be used instead - and these euphamisms are usually complimentary in case the entity in question hears anyway. Even the English word bear is meant to be derived from a euphamism for a word that our Germanic ancestors were afraid to speak in case it attracted the real thing.
Game and Story Use
- Many GMs have a hard time making up names on the spot. Use one of the random name generators above  to create random names in advance.
- In any setting with the correct forms of magic, the names of spirits and demons can be valuable as noted above.
- Worth having a mechanical model for their utility - whether it just grants a bonus to attempts to bind and compel them or is more effective than that.
- The name as title thing is interesting as well - especially given the possibility of a title being usurped. A good example is found in the Hellboy novels where the demon Ualac learns Hellboy's true name (Amun ah Rama) and uses it to bind him and steal the mystical crown of (usually invisible) power that he possesses. Unfortunately for Ualac, Amun ah Rama translates as "Wears a crown of fire" … and by stealing the crown, he also stole the name and subjected himself to the power of the binding … whilst in the presence of a very angry Hellboy.
- Again, The Dresden Files notes that true names make magic a lot easier, but that they don't work nearly as well on mortals because mortals keep changing and are not the same thing tomorrow as they were yesterday … although a mortal's true name may not change, the bonus should fade over time.
- Which come to think of it, could make a properly timed marriage very effective for a female practitioner. (Consider in some hypothetical Dresden-prequel a triumphant enemy of Margaret LeFey bearing down on her with "Margaret Gwendolyn McCoy I bind you…" "Call me Mrs. Dresden" "Wha.. <splat>".)