Vc precisara de um cartão de crédito internacional, pagará US$ 499,00 e o link para o certificado do tipo certo é este aqui:
A Verisign brasileira em nada pode te ajudar, é com a Americana que vc vai comprar.
Após o pagamento, eles te pedem 48 horas para checar algumas coisas, ligam pra vc (em ingles) e fazem 1 ou 2 perguntas só para confirmar e depois te mandam no seu e-mail um arquivo texto que é o certificado.
Com base nele, vc cria um keystore, importa para dentro e a partir daí esta apto a assinar (pelo prazo de validade que vc comprou) a aplicação em qualquer IDE ou no braço mesmo.
[editado]
Antes de vc comprar no site da Verisign, vc deve gerar na tua maquina um arquivo CSR que contem dados basicos seus que vao constar depois no certificado emitido. Coisa baba mesmo, é só olhar no javadoc do jarsigner e não tem erro.
Outra coisa importantíssima e vc ver se na especificação do aparelho diz que ele aceita verisign ou UTI Root. Se não tiver um dos dois, é quase certo que o certificado da Verigsign nao vai servir, tem que ser de outra empresa que o celular suporte.
[/editado]