If you are using Eclipse for Development just right click on your project and click export. Now choose Android and then Export Android Application. In the next step confirm the project that you want to export. Then click next and now you should be able to select create new keystore. Now fill in the required fields and your should be able to sign your app. Be sure to make a backup of the keystore file and remember your password. Losing this will make it impossible to update your application.
If you are using the terminal to create a keystore and you have Java SDK installed there should be a program called keytool in /usr/bin (on a unix based system). On Windows the SDK should also come with the keytool but the install location may be different search for keytool.exe on your computer if keytool is not in your path already. With this tool you should be able to create a key in the following way:

keytool -genkey -v -keystore my-release-key.keystore -alias alias_name -keyalg RSA -validity 10000

Remember that once you lose your Certificate or it expires you will not be able to sign your application. Make sure that the expiration date is a long long time in the future.