The first time I went to publish an Android app it was unclear how to export an apk. I also thought if the app was free I wouldn't need to do anything special to the final apk, but as it turns out you still need to sign the apk before the google market will let you upload it.
The video below is a simple walk through showing how to version/build/sign/export your apk for the google market. It's under 5 minutes and straight to the point.
If I left anything out be sure to leave a comment.