Inclusion Criteria:

          -  Participants must be age ≥ 3 and ≤ 30 years, and have had a histologic diagnosis of
             osteosarcoma, Ewing sarcoma, or rhabdomyosarcoma or non-rhabdomyosarcoma soft tissue
             sarcoma either at diagnosis or relapse. Must have experienced relapse after front-line
             therapy, or have had documented disease progression during front-line therapy.

          -  Must have measurable disease that can be assessed using Response Evaluation in Solid
             Tumors (RECIST) 1.1, defined as the presence of at least one lesion on MRI or CT scan
             that can be accurately measured with the longest diameter of 10 mm in at least one
             dimension. For this phase II trial, patients with disease limited to bone or marrow
             metastases are NOT eligible, as disease at these sites cannot be assessed by RECIST
             1.1 criteria.

          -  Must have relapsed or refractory cancers for which there is no known curative option.

          -  Prior Therapy: There is no limit to the number of prior therapies provided all
             eligibility criteria are met. However, participants must have recovered from the acute
             toxic effects of all prior treatment. (A) Must not have received prior therapy with
             either gemcitabine or nab-paclitaxel. (B) Myelosuppressive chemotherapy: Must not have
             received myelosuppressive chemotherapy within 3 weeks of protocol therapy on this
             study. (C) Hematopoietic growth factors: 7 days must have elapsed from the start of
             protocol therapy since the completion of therapy with filgrastim, and 14 days must
             have elapsed from the start of protocol therapy after receiving pegfilgrastim. (D)
             Biologic (anti-neoplastic agent): 7 day must have elapsed from the start of protocol
             therapy since the completion of therapy with a biologic agent. (E) Monoclonal
             antibodies: 3 half-lives must have elapsed from the start of protocol therapy since
             prior therapy that included a monoclonal antibody. (F) Radiotherapy: 2 weeks must have
             elapsed from the start of protocol therapy since local palliative radiotherapy (small
             port); 3 months must have elapsed if 50% radiation of pelvis; 6 weeks must have
             elapsed if other substantial bone marrow irradiation was given. (G) Stem Cell
             Transplant or Rescue: No evidence of active graft vs. host disease and 2 months must
             have elapsed from the start of protocol therapy since transplant.

          -  Karnofsky performance score must be ≥ 60

          -  Must have organ and marrow function

          -  Neuropathy: Must have ≤ grade 1 neuropathy at enrollment

          -  Central nervous system (CNS) Metastases: Potential participants with known CNS
             metastases are excluded unless treated surgically or with radiotherapy and stable with
             no recurrent lesions for at least 3 months from the start of protocol therapy.

          -  Contraception: Women of child-bearing potential and men must agree to use adequate
             contraception prior to study entry and for the duration of study participation. Men
             treated or enrolled on this protocol must also agree to use adequate contraception 4
             months after completion of gemcitabine and nab-paclitaxel administration.

          -  Consent: Participants must have the ability to understand and the willingness to sign
             a written informed consent or assent document.

        Exclusion Criteria:

          -  Potential participants who are receiving any other investigational agents

          -  Must not be receiving any additional medicines being given for the specific purpose of
             treating cancer

          -  A history of allergic reactions attributed to docetaxel or paclitaxel

          -  Concomitant Medications: The metabolism of paclitaxel is catalyzed by CYP2C8 and
             CYP3A4. The following medicines should be avoided on this study because of their
             ability to inhibit or induce with CYP2C8 or CYP3A4: A) Inhibitors: ketoconazole and
             other imidazole antifungals, erythromycin, fluoxetine, gemfibrozil, cimetidine,
             ritonavir, saquinavir, indinavir, and nelfinavir. B) Inducers: Rifampicin,
             carbamazepine, phenytoin, efavirenz, and nevirapine. C) Potential participants
             receiving any of the above medications are ineligible.

          -  Potential participants are ineligible if they have uncontrolled intercurrent illness
             including, but not limited to: ongoing or active infection; symptomatic congestive
             heart failure; unstable angina pectoris; cardiac arrhythmia; psychiatric
             illness/social situations that would limit compliance with study requirements.

          -  Pregnant or breastfeeding

          -  HIV Infection: HIV-positive patients on combination antiretroviral therapy are
             ineligible because of the potential for pharmacokinetic interactions with the study
             medications.

          -  Anyone who in the opinion of the investigator may not be able to comply with the
             safety monitoring requirements of the study.