Helping people with computers... one answer at a time.
Sometimes it might seem like everything's infected, but with a few steps and preparation you can work, surf and use the internet safely.
Everything Java is not infected.
I know that reading all the dire warnings you might see every day might make it seem like just turning on your computer is an exercise in dangerous futility, but it's just not that bad. With a little caution on your part (and perhaps a better security system), you can use the internet, including Java, quite safely.
I want to address a statement you made in your question: "My security system made me remove all Java from my PC." My initial reaction? That's just wrong. I don't know exactly what security system you're running, or what it saw that it decided to have you take that action, or if perhaps there was a misunderstanding, but removing Java from your system is not a viable solution.
Java, like any technology on your computer, can be used safely and to great effect. It can also be abused and infected, of course, but removing it is rarely the answer. Reinstalling it perhaps - or in the worst case reinstalling your entire operating system, but the net result is that you can have a safe system running Java.
So I can't really comment on how you got to where you are, since details are not included.
But I can recommend on how to proceed, and it's mostly the standard safety to-do list that I've talked about several times.
Start with a clean system. If I had to hazard a guess, your security software did detect an infection and attempted to remove it. If that's the case, the "right" thing to do is to reinstall the software. Perhaps even reinstall Windows itself to remove all traces of the infection.
Keep the System Up-To-Date. Turn on Windows automatic updates. Java, itself, has an automatic updater that you should let run, and should allow to update when needed. Essentially, you need to make sure that all the software on your machine is as up-to-date as possible. Why? Because all software vendors are fixing bugs that could be exploited to infect your system with malware. Installing the updates removes those vulnerabilities.
Get behind a firewall. I don't really care if it's a router or a software firewall, or even if all you do is turn on the Windows firewall, just do something. (OK, I do prefer a router, if that works in your scenario.) A firewall is an important first step in protecting your system from an entire class of malware.
Get better security software. Like I said, I don't know what you're running or what it told you to do what it did. It sounds like you're running a suite, and I have to say that I really don't believe in all-in-one security suites - I just keep hearing that they cause more problems than they're worth. I would get a separate anti-virus product and an anti-spyware product, make sure that they are up to date, and make sure that the databases that they use are also being updated regularly.
Those are the biggies. I have more on the subject in Internet Safety: How do I keep my computer safe on the internet? - I strongly recommend you read that as well.
The bottom line is that there's no reason you can't pull together a system that will allow you to browse and use the internet - including Java based technologies - safely. It just takes a little preparation and planning.