From Android Wiki
When publishing an app for everyone to use, be it with a custom ROM or on the Android market, you need to sign the .apk with a personal private key. The old way of doing this was to use keytool and then sign it with jarsigner, but the way detailed below is a lot easier for most people and uses a standard toolset that should be available on almost any operating system.
One tool for signing .apk is a utility aptly named "SignApk.jar", which is just about the easiest way to sign .apk files. SignApk.jar comes with some test keys, but it's generally advised that you generate your own. The steps below can be used to create some personal private keys and a certificate for use with SignApk.jar.
The "SignApk.jar" file may be downloaded from the Git repo, or you can use Google to search for "AndroidMod.zip download", which also contains the tool.
openssl genrsa -out key.pem 1024 openssl req -new -key key.pem -out request.pem openssl x509 -req -days 9999 -in request.pem -signkey key.pem -out certificate.pem openssl pkcs8 -topk8 -outform DER -in key.pem -inform PEM -out key.pk8 -nocrypt
Then, you can sign an .apk file using the SignApk.jar tool and the key.pk8 and certificate.pem files you created
java -jar SignApk.jar certificate.pem key.pk8 Application.apk Application_signed.apk
The Old Way
(What was wrong with this way? It uses standard JDK tools, and is still the recommended approach according to the docs at developer.android.com.)
Create A Keystore
First, create your signing key. In the command below, give a name to the keystore filename as keystorename, a keystore password as keystorepassword, an alias for identifying the key as keyalias (note the validity period has been set to the Google recommendation of about 25 years), and substitute your name, company name and location in the obvious places:
keytool -genkeypair -keystore keystorename -storepass keystorepassword -keyalg RSA \
-validity $((25 * 365)) -alias keyalias -keysize 2048 \
-dname "CN=J Random Hacker, O=HackerCo, L=Anytown, ST=Anystate, C=US"
Sign A Package
Now, each time you build a package, you can sign it as follows:
jarsigner -verbose -keystore keystorename apkfilename keyalias
where keystorename is the name of the keystore you previously created with keytool, keyalias is the alias you previously assigned to the key, and apkfilename is the package already built but not yet signed. You will be prompted for the password you previously assigned to the keystore, and the package file will be updated with signature information in-place.
Alternatively, you can type
jarsigner -verbose -keystore keystorename -signedjar signedapkfilename apkfilename keyalias
and it will leave apkfilename unmodified, and generate a new signed package as signedapkfilename.
You can verify the package has been signed with this:
jarsigner -verify -verbose -certs apkfilename
This will display appropriate information next to every entry in the package file that has been signed.