After Unity to Windows 8 Checklist and Unity to iOS Checklist, this is the Andriod version:

To test on Andriod devices you will need to download the ‘Andriod SDK’ which also requires “Java SE Development Kit”. you need to download a “platform” from your Andriod SDK folder under “tools/andriod”. After that, still in your SDK folder you have to copy the file in the folder “build-tools/ [build number you downloaded] /zipalign” and paste it into the “tools” folder.

Sadly, after many days of frustration, I could get it to export the apk file in Mac and but it did work on Windows. Below are some things I tried in Mac that did not help:

Something else that seems required to get the Java to work is in Terminal, paste this line in to find where the jdk file:
/usr/libexec/java_home

Copy the resulting line somewhere. Then in terminal paste this:
/usr/bin/open ~/.bash_profile
to open a file up

export JAVA_HOME=[the thing you copied in the first step]   
export PATH=$JAVA_HOME/bin:$PATH

I’ll have to update this post when I get it working for Mac.

Anyways, one thing you have to do to get the apk to the Google Play Store is sign it. Fortunately it’s much much more straight forward than iOS. In Unity under Build Settings/Player Settings/Publishing Settings. You create a keystore file for you and then a key for your game. Think of a password for both and store them somewhere for future use. Also don’t forget your icons. It is recommended to tick the ‘override for Andriod’ since you’ll want an png with transparency around it.

Also if you have to make multiple uploads of the same version (eg. to edit the icon) make sure to go to Build Settings/Player Settings/Other Setting and increase the “Bundle Version Code’ by 1. It has to unique and higher than the existing apps bundle version code.

A way to test the app on a device to is to upload the apk file to something like http://www.apkinstall.com/ and then use your device to scan the QR code generated.

You’re now ready to export your apk file.

The screenshots are much more lenient in the sizing so I just reuse the ones for iOS.