According to their homepage, Java Verified "is the industry-recognised Java testing and signing programme." To me it sounds like another "gimme your money and we'll do some testing and the give you a nice Foo Compliant Approval Seal of Exellence".
Is it something you'd expect to have for your Java ME app? Would it make a difference to your application? And most importantly, would anybody care?
What's your advice?
It's a certification endorsed by AT&T, LG, Motorola, Nokia, Oracle, Orange, Samsung, Sony Ericsson and Vodafone but owned by Oracle. There is extensive documentation at their site so a little reading should give you a pretty good idea of what is involved.
I get the feeling that most individuals and small businesses won't care too much about this certification but larger corporations and government organizations may. Many large businesses will only buy software that comes with a certain degree of certification of some kind.
You can probably rest assured that Oracle has already familiarized many large organizations with this certification and have suggested that they look for products with it. Your best bet would be to be familiar with it, but don't worry about getting your app certified until you encounter a specific request for it from a potential customer. You may also want to consider it if other well performing apps in your market have it.