Lead records are created in the Marketo database when you add them manually, you import lists, someone fills out a form, or they sync over through an API like SFDC integration or a Webinar adapter. You can find more details by checking out the Help Articles section.
We've setup what I call a 1:1 mirror between SFDC and the MKTO databases (so they match) using a triggered campaign that syncs a new lead to SFDC on creation. Depends on internal business processes, but most companies prefer to bake leads a bit longer and only sync what we call "marketing qualified leads" to their CRM.