I made a couple of resource posts on choosing medieval names for reenactors recently, and sylvaine suggested that I share them here, too.

• Name construction and Appendix A is a guide to using Society for Creative Anachronism resources to get quick-and-dirty name grammar guidelines for a particular medieval culture.
  
• Browsing for historical name data walks through the kinds of searches I do when I'm trying to find raw data on names from a particular time and place, using medieval Bohemia as an example.
  
• I should also mention The Medieval Names Archive, which I maintain!