C'è Skebby, un software che gira sui telefonini che supportano J2ME, che fa quello che vuoi fare tu. In sostanza Skebby non fa altro che sfruttare uno o piu account preventivamente creati sui siti dei vari operatori telefonici che permettono di inviare un certo quantitativo di SMS gratuiti al giorno. L'applicazione crea una connessione HTTP verso uno di questi siti il quale poi spedisce il SMS (il cui body e destinatario saranno presumibilmente passati come parametri della richiesta HTTP).
Se possiedi un cellulare che 'riconosce' i comandi AT&T potresti interfacciarti ad esso attraverso le javacomm API. Attraverso i comandi AT&T puoi 'dire' al tuo cellulare di inviare un SMS come se lo facessi attraverso la tastiera.
Ciao