How to make new backgrounds is in the Dungeon Master's Guide in the “Creating New Character Options” section that starts on page 285. How to make new backgrounds is on page 289.
If the players will be creating the new backgrounds' concepts, you should work with your players on the mechanical details, not let them choose them on their own. Creating new backgrounds is potentially quite powerful in the hands of a self-interested player, and they shouldn't be let loose like kids in a candy shop. Let them do Steps 1 and 2 in consultation with you to determine theme and flavour, and then you do Steps 3 through 5 yourself to determine mechanical benefits, and then consult with them to see if the result suits the theme.