certified android devices are those you can get in most stores. the play store is important for many people, ajd many apps don’t work correctly without the google mobile services components, and device makers can only legally install these on their phones if they certify their device. the certification process requires an array of quality controls and restrictions.

How can they enforce this for apps not on the play store?

certified devices will need to integrate an app verifier that will check if an app has been approved by google. the public AOSP project is said to also get this, but anyone basing on it can rip it out or modify it to their advantage. but certified device makers don’t have a choice thn to include this restriction.

Like if I write my own APK will my phone just refuse to run it if I don’t go through some paperwork with Google?

what we know so far, apps you made can be installed through a development tool. but app store aps like fdroid don’t have access to this tool, it’s difficult to enable, and somewhat risky too