Java download

I can't help you with the virus, but download the Java JRE or JDK only from the manufacturer, Sun Microsystems, at java.sun.com.

There would be no "embedded virus" in a legitimate download of the Java Runtime Engine. To ensure no unwanted baggage, download only from primary sources whenever possible. Java's own download page is HERE. BTW, at time of this writing, the current version is at Update 8.

Java download
I did go to Sun Microsystems to download a Java program. Would it be possible that the old Java that was on the machine had a virus?
My AVG free reports the following messages when I run it:
Counter.class virus identified Java/byte verify C:\Documents a...
Verifier Bug Class Virus identified Java/byte verify C:\Documents a...
Web.exe Trogan horse Generic. UFN identified Java/byte verify C:\Documents a...
Worker.class identified Java/byte verify C:\Documents a...
Xeyond.class identified Java/byte verify C:\Documents a...
jar.jar -2ad 522e1-6c 267 identified Java/byte verify C:\Documents a...
and then it goes on to tell me that the virus is embedded and can not be removed.
Littledear

That just mught be a false positive - though its also possible there's something there. See whatchya come up with via a couple on;ine scans. I recommend you try a runthrough with both Trend Micro's HouseCall and Panda's ActiveScan. Which order you do them in is unimportant, but before running either, be sure to turn off or disable any resident security/privacy software you might have, including pop-up and ad blockers, and to run the scans with no other browsers open or apps running. If you report back with the results of both scans - including, verbatim, all error messages and/or "could not clean" notices if any, we prolly can tell a lot more.

Oh, and before doing anything else, clear your Java cache -

Start>Settings>Control Panel>"Java Plug-in Control Panel"
Select the "Cache" tab
Click "Clear button in the "Cache Tab to clear your JRE cache.

And of course clear cookies and files in the "Temporarary Internet Files" panel on the "General" tab of the "Internet Options" Control Panel - and do that from Control Panel (with no browsers open), not from Internet Explorer's toolbar.