Cara, com JME é possível, mas somente com CDC.
CDC é a Connected Device Configuration, que é uma configuração bem mais avançada que a CLDC. Ocorre que são poucos os aparelhos usuais que têm suporte à CDC. Exemplo: não conheço nenhum aparelho celular que suporte CDC, o mesmo vale para PalmTop. Caso você vá usar um aparelho que suporte CDC (o que seria excelentemente bom), então o acesso direto ao banco de dados fica bem fácil, uma vez que passa a depender basicamente do Driver, assim como na JDBC JSE. OBS.: se não me engano, a JDBC suportada no JME CDC é a 3.0 (com algumas limitações).
Claro que, caso o aparelho de seu propósito não suporte CDC e, como é o mais provável, seja CLDC você pode fazer como o colega acima citou, fazer algum manejamento de dados a fim de manipular o banco de dados. WebServices é uma alternativa excelente, claro que ainda existem outras, como sincronização sem fio com um terminal ativo no PC via Bluetooth ou IR, ou ainda troca de dados simples via Web comum, via XML por exemplo.