When using Visual Studio 2015 Update 3 with the latest Xamarin tools (which is v4.2.2.6 when writing this answer), right click your Android project and select “Archive…” as described here:
https://developer.xamarin.com/guides/android/deployment,_testing,_and_metrics/publishing_an_application/part_1_-_preparing_an_application_for_release/#Compile
This will open the Archive Manager and begins the process of archiving the App bundle. When the archiving is finished, you can click on the button “Distribute…” at the right bottom corner of the Archive Manager to create a signed APK. This is described here:
https://developer.xamarin.com/guides/android/deployment,_testing,_and_metrics/publishing_an_application/part_2_-_signing_the_android_application_package/
Note: if you do not use a signed APK, you will probably get a parse error if try to install on an Android device.