x509 Certificate Signature
Signing with "md5WithRSAEncryption" means CA calculates MD5 hash to get an integer first and apply his private RSA key next to produce the signature. A DER-encoded string is the input to the hash. Client (Subject in X.509 parlance) data, including public key, is described with ASN.1 language, "to be signed" part of specification. Certificate extensions (v3) are also included into "to be signed".

"Plain" public key, as received from client, is encoded according to X.509 specifications. See ASN.1 description at PKCS 10, "certificate request".

Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile
Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile