After about 1.4 we started using an auto-updater the way windows does, so if they have instaqlled at elast 1.4 they shoudl be automaticly updated to 1.5 or later.
If they havent not installed a 1.4 vm them you will need to get them to download it. what percentage of your amrekt this will be is a bity unrepdictable because it depends on your market dynamics. For the past year or so I believe more then 50% of new PCs have shipped with the VM. Older PCs are more of a crap shoot.
Edit: I should mention that if what you want to use is 1.5 prgorammign constructus but don’t actually need 1.5 API calls, you might try a tool one of the guys wrote her that messages JDK1.5 byte code back into a form executable by earlier VMs. I forget the name but Im sure someone around here remembers…