Here is what you do to create a new key and to sign your app for distribution.
1) Right-click on your project in the Package Explorer section of Eclipse and select Android Tools > Export Signed Application Package...

2) Go through the wizard, make sure your project is selected as the one to export
3) Next step is to create a new keystore. Specify the path and what you want the password to be

4) You can change the alias if you want, but default is "android" which is sufficient. Set a password for this alias, set the validity of this key (between 0-1000 years), and at least your first and last name. You can also add any other details you want associated with this key (not required, however).

5) Finish the procedure by specifying the path to where you want to export your APK to be. Press Finish, Eclipse will take a while to package your app. Once it's done, you'll have your new key at the path you specified, as well as an APK file signed by that new key.
Let me know if that helps!