MSDN lists a walkthrough (click here to see it) (it's related to CRM Online 2011, but since most of the info is still accurate I'd say it's worth a try) aimed exactly at connecting to CRM Online fom Java.
The prerequisites listed are
Java SE SDK 1.6 update 23 or later
Eclipse 3.7.x and above or NetBeans 6.9x or later
Apache Axis 2 ver. 1.6.1
Apache HTTP Components Client 4.1.3
Microsoft Dynamics CRM Online
You're going to have to generate the classes (in .NET you use crmsvcutil.exe
, it's roughly equivalent) and then you should be all set.