How android apk file signing works? There are a number of pages on web to tell how to sign apk file for Android. But none I've found telling how it works under-the-hood. The (e.g from here https://github.com/appium/sign) command is java -jar SignApk.jar testkey.x509.pem testkey.pk8 my.apk my.s.apk and it has two files with keys - .pem (certificate) and .pk8 (as far as I understood it contains private key).  

Official Android docs page app-signing says "Android requires that all APKs be digitally signed with a certificate". But certificate contains public key...  

Do they mean app should by signed (presumably hash with private key) + with certificate (which is plainly attached to apk file)? That would explain why command above needs two files...
The APK signing is well documented by Android, actually:


You have here a high level overview of the process. 
A new APK signature scheme (v3) has been introduced with Android 9, that is detailed  here. However notice the v2 can still be used.


The documentation about v2 has a good overview of what is contained in a signature block in an APK:


  For each signer, the following information is stored:   
  
  
  (signature algorithm, digest, signature) tuples. The digest is stored to decouple signature verification from integrity checking of the APK’s contents.
  X.509 certificate chain representing the signer’s identity.
  Additional attributes as key-value pairs.
  


Now, what does that mean?

Well, the signer has to own the secret key corresponding to a certificate, that has to be verified by some Certificate Authority. The signer can then sign an APK and has to bundle their certificate chain inside of the APK, so that anyone can verify the certificate chain, and if it checks out, then check that the signature verifies under that certificate. 
And the certificate is required in order to be able to link the public key we are using to verify that APK with a given identity. (Because otherwise, without certification, you have no link between a given secret/public key and an identity.)

Here "digitally signed with a certificate" is a misuse of language to mean that one is signing the APK using the private key corresponding to a public key stored in a certificate.

This is effectively done in practice by computing the signature of a digest (a hash) of the  of APK contents that is computed as indicated here.