The goal of this clinical research study is to learn if the vaccines, gp100(g209-2M), and MAGE-3, when given in combination with resiquimod (R848), can help to stimulate the immune system against melanoma.

The Study Drug/Vaccines:

Resiquimod (R848) is designed to increase the production of antigen-specific T-cells, to activate immune cells, and to increase T-cells going into the tumor, which may cause the tumor cells to die.

gp100(g209-2M) and MAGE-3 are vaccines designed to stimulate immune cells, also called T-cells, which may help the immune system to recognize and kill melanoma cells.

Study Groups:

If you are found to be eligible to take part in this study, and you have metastatic melanoma, you will be assigned to Group 3. If you have had the melanoma removed and want to be treated to try to keep it from coming back, you will be randomly assigned (as in the flip of a coin) to Group 1 or 2.

• If you are in Group 1, you will receive the vaccines gp100(g209-2M) and MAGE-3 and R848 for 8 weeks. After 8 weeks, if you have melanoma lesions, you will apply R848 to half of the lesions on your body for 16 weeks.
• If you are in Group 2, you will receive only the vaccines (gp100(g209-2M) and MAGE-3) only for 8 weeks. After 8 weeks, if you have melanoma lesions, you will apply R848 to half of the lesions on your body for 16 weeks.
• If you are in Group 3, you will receive the vaccines gp100(g209-2M) and MAGE-3 and R848 for 8 weeks. After 8 weeks, if you have melanoma lesions, you will apply R848 to half of the lesions on your body for 16 weeks.

After 8 weeks, if you no longer have melanoma lesions, you will have completed the study treatment.

Study Drug/Vaccine Administration:

Once a week for 8 weeks, you will receive the vaccines, gp100(g209-2M) and MAGE-3, intradermally (through a needle into your skin) and subcutaneously (through a needle under your skin) at 2 separate sites in separate extremities. Half of each dose will be given one way, and half given the other way. These vaccines will also be given on the same day. You will receive a total of 4 injections each week.

If you are in Group 1, every time you have the vaccine injection, R848 will be applied as a gel over the gp100(g209-2M) injection site. The R848 gel will be allowed to air dry for 30 minutes and then covered with a gauze dressing which remain on overnight.

After 8 weeks, for participants with melanoma lesions, 2 times a week for 16 weeks, you will apply the R848 gel to half of the lesions on your body. You will be given written instructions and a "hands-on" demonstration on how to apply the gel. You will also be given a worksheet to help you with applying the gel.

Study Visits:

One day after your first dose of vaccine (Day 2), you will have a punch biopsy of the vaccine injection site to check your immune system. A punch biopsy is when a hollow instrument that is used to remove a small coin-shaped sample of tissue.

At Week 2, the following tests and procedures will be performed:

• You will have a physical exam, including measurement of your vital signs and weight.
• Your performance status will be recorded.
• Blood (about 1 teaspoon) will be drawn for routine tests.
• Blood (about 4 tablespoons) will be drawn to study your immune response to the vaccine combinations.
• You will have a punch biopsy of the injection site to check your immune system the day after the vaccine is given.

Every 4 weeks, the following tests and procedures will be performed:

• You will have a physical exam, including measurement of your vital signs and weight.
• Your performance status will be recorded.
• Blood (about 1 teaspoon) will be drawn for routine tests.
• Blood (about 4 tablespoons) will be drawn to study your immune response to the vaccine combinations.

Every 8 weeks, for participants with metastatic disease, the following tests and procedures will be performed:

• You will have CT or PET/CT scans of the chest, abdomen, and pelvis to check the status of the disease.
• The tumors will be measured and photographed. Your private areas will be covered (as much as possible), and a picture of your face will not be taken unless there are tumors on your face.
• If the doctor thinks it is necessary, the tumors will be measured by CT scan.
• If the doctor thinks it is needed, you will have an MRI/CT of the brain to check the status of the disease.

The day after you first start the gel (Week 8), you will have 2 punch tumor biopsies to check your immune system. One biopsy will be of a lesion with the R848 and one without, if it is available. For participants without disease, the study will be completed and your follow-up will be decided by your doctor.

At Week 0 (before vaccine is started), after treatment at Week 8 (+/- 1 week)., and Week 16 (+/- 1 week), white blood cells will be collected by leukapheresis to test for antibodies. If you have the leukapheresis, blood (about 2 teaspoons) will be drawn as well. If you do not have leukapheresis, blood (about 4 tablespoons) will be drawn instead.

The leukapheresis procedure is research-related and would not be performed as standard of care if you were not on study. Blood for the leukapheresis will be taken through a needle in a vein in one of your arms. A solution will be added to keep your blood from clotting while it goes through the machine that collects and removes white blood cells from your blood. The remaining blood is returned to you through a needle in a vein of your other arm. This is may take up to 3-4 hours. Although several pints of blood will go through the machine, only about 1/2 a pint (1 cup) will be in the machine at any time. If you cannot have a needle in your vein, this blood will be removed thorough a central venous catheter (CVC). A CVC is a sterile flexible tube that will be placed into a large vein while you are under local anesthesia. You will be given another informed consent document to sign, which describes the risks of the CVC and the care involved.

Length of Study:

You will continue to receive treatment for up to 4 6 months, as long as you may benefit from the study and are responding to the gel. You will be taken off study if the disease gets worse or you experience any intolerable side effects. If you are in the group without disease, you will not receive the study treatment.

Follow-Up:

All three groups will be called 1 time a month for 12 months after coming off the study drugs to check on the status of the disease.

This is an investigational study. The study drugs/vaccines gp100(g209-2M), MAGE-3, and R848 are not FDA approved or commercially available. At this time, they are only being used in research.

Up to 71 participants will take part in this study. All will be enrolled at MD Anderson.

Inclusion Criteria:

1. HLA-A*0201 positive (to enable immunization with the HLA class I restricted gp100(g209-2M) peptide). Stage IIB or IIC patients will be enrolled after review and approval by the PI. (a tool to determine the projected survival at 5 years, like, but not limited to, the nomogram at www.melanomaprognosis.org. If the projected survival is less than 50% at 5 years, then the patient is considered for enrollment. This is with the recognition that the adjuvant, if effective offers a significant impact in that group of stage II patients.)
2. Patients >/= 18 years old with histologically documented metastatic melanoma with a. (Metastatic disease cohort) Measurable disease, stage IIIB, IIIC (in transit lesions with or without nodal metastases) that includes lesions accessible for biopsies or IV M1B b. (Adjuvant cohort) subjects who are NED and stage III or IV. This includes patients with stage IV disease resected to NED. Stage IIB or IIC patients will be enrolled after review and approval by the PI.
3. Eastern Cooperative Oncology Group (ECOG) performance status of 0-1
4. At least 2 biopsiable easily accessible cutaneous and subcutaneous lesions in patients in the metastatic disease cohort
5. White Blood Count (WBC) >/= 3000/mm^3 (part 1 & 2)
6. Platelet count >/= 90,000/mm^3 (part 1 & 2)
7. Serum alanine aminotransferase (ALT) and Aspartate Aminotransferase (AST) \

every 2 weeks through Week 4, then every 4 weeks during the vaccination treatment, up to 8 weeks