Licensed Genealogist - Truth be told, there really isn't such a thing in most jurisdictions. Licensure generally implies compliance with local laws regulating businesses and isn't specific to the genealogy profession. It may mean that the genealogist follows local laws and a code of ethics, but does not in any way imply competence as a genealogist. Some people do use the term 'licensed' as a synonym for 'certified,' however, so be sure to ask anyone using this title exactly what they mean by it.
Professional Genealogist - This title generally applies to any genealogist with knowledge and experience of proper genealogical research methods and techniques, and who supports and upholds high standards in the field of genealogy. People who call themselves professional genealogists are usually either certified or very experienced, but this is not always the case. Anyone can use the title "professional," so be sure to inquire about their education, experience, and references.
Accredited Genealogist - This accreditation program, originally developed by the Family History Department of the Church of Jesus Christ of Latter-day Saints and now administered by the International Commission for the Accreditation of Professional Genealogists (ICAPGen), tests individuals on both theoretical research methodologies and in the location and use of original documents unique to the regional area in which they have applied for accreditation. Applicants for the program are required to sign a code of ethics and must renew their accreditation every five years. Genealogists who have met the rigorous requirements are bestowed the title of Accredited GenealogistSM (AG).
Certified Genealogist - The Board for Certification of Genealogists tests and certifies researchers in the U.S., Canada, and other countries around the world. Certification categories include Certified Genealogist (CG) and Certified Genealogical Lecturer (CGL). Genealogists certified by the BCG must pledge to a code of ethics and conduct, and renew certification every five years. Similar screening and certification programs exist in other countries with different titles, so be sure to ask about the use of any postnomials with which you are not familiar.
Certification and accreditation are not a requirement for genealogists who wish to accept clients, but they do help you to know that these individuals have had their competence as a genealogical researcher thoroughly tested by their peers. On the other hand, the fact that a genealogist has not chosen to pursue certification/accreditation doesn't mean that they aren't extremely skilled and professional in their genealogy research. Ultimately, the responsibility for locating and evaluating the credentials of anyone you hire to research your family tree is up to you.