Do both mean the same thing ("maybe")? If so, when is "быть" added?
Может is the declension of the verb мочь into 3rd person singular. Мочь means 'can, to be able'. Быть means "to be", so a somewhat literal translation of может быть would be "it can be", which is synonymous with "maybe" or "perhaps".