You don't, actually, most sites are discovered organically through links on other sites. Submitting links hasn't been common since the days of Yahoo and DMOZ.

You're right that "consent" is the important legal issue, but it's usually implied based on what your site requires re: authentication/authorization, robots.txt, and the controls Google has provided to let you tell them not to index a site.

Nope - it just requires someone to link to you. Since there are informational sites that list new domains, that might happen automatically.