First verify the domain ownership in the Google Search Console then create the mapping in Cloud Run. Cloud Run will show the required DNS records. Add these records in Cloudflare.
This is where I got stuck. Even after adding the records, Google would not provision the certificate.
What worked for me was setting all the previously added DNS records in Cloudflare from Proxied to DNS Only. In addition, I also set the SSL/TLS encryption mode to Full (strict). I'm not sure if the latter helped but it only worked after doing it. Then I waited for about 20 minutes for the certificate to be provisioned. After it is provisioned, it is okay to change the DNS records back to Proxied in Cloudflare.
Google should really get around to improving the domain mapping process for Cloud Run. As it is now, it is confusing and does not give any information on what went wrong. Although the following CLI command does give a little bit more information than in the cloud console:
gcloud beta run domain-mappings describe --domain {domain}