Using modeling clay or Model Magic and objects like ferns, feathers, bones, or shells, you can create a fossil.
We just did this at the library and made all kinds of impressions from shells to toy dino prints to car tracks.
Flatten a piece of clay with your hand and press an object into it. You can just stop here and let the clay or Model Magic to dry and then paint it. This is how foot prints are fossilized.
If you are ready for a more realistic fossil, you can use plaster or clay. Carefully roll out another piece of clay about the same size. Cover the object with the second piece of clay and be sure it molds to the object. Gently pull the clay apart and you will have two impressions of your fossil! Once dry, you can paint the clay to look like rock.