Most of the solid material in a plant originally comes from the atmosphere. Through a process know as photosynthesis, plants use the energy in sunlight to convert carbon dioxide from the atmosphere into simple sugars. These sugars are then used as building blocks and form the main structural component of the plant.
Plants also rely on soil or dirt to get other nutrients like nitrogen and phosphorus. Interestingly, it turns out that the soil near the north pole of Mars is surprisingly Earthlike, with a pH not unlike many vegetable gardens. Read more here, here or here.
Plants also need water, so if it was a few billion years ago when rain used to fall on Mars we might have been able to grow a garden. Oh well, an opportunity lost I suppose.
