I'm working on OSX and my server is Linux. I've downloaded the Linux package here that I want to use and install, but without using SSH I don't see how I could install it. I would use SSH, but I only have the basic hosting plan and cannot move up right now. Is there a way I am not aware of, or am I out of luck here?

I tried everything I could think of in the Terminal, and so far nothing. Any help would be great.

As FloralL mentioned, you can add SSH to your Basic plan at any time.

Do you really need command line access (SSH), or can it be done in a batch job? If the latter, "cron" can be used to fire off commands (so long as you don't need to provide interactive inputs to the program).

Finally, are you looking to run  a Java program as part of your site (rather than providing it as a downloadable file)? If so, you may need to get Java Server Pages set up (another monthly fee). I don't think the the Basic plan will run Java programs "straight out of the box". You might want to discuss this with Support before you go pouring money into these extra features.