Hi Ali,
The process may be a bit more complicated than you imagine, but since you didn't say how you tried to do it let me suggest the following:
1. You want the roots to grip the rock as tightly as possible. For this reason it is best to start with small material, like a seedling or a cutting that has been rooted for a year or so. If the roots have a lot of wood to them you wont be able to shape them to conform to the stone. A good root over rock will have the roots start to change out of round shape due to the grip on the rock.
2. The Rock - generally you should choose a stone that you would want to look at even if there was no tree involved. Don't just pick up some random rock, look for something with some color and interest. The stone has to be pretty durable - otherwise the tree may crush it as it grows or it will crumble as the years pass and you'll loose the interesting parts.
3. Bare root the young tree (hence you should only do this during repotting season) Place the roots over the rock in the way that you want them to stay - consider carefully because its really hard to move them after they are allowed to grow out. You want them to conform to the stone closely, it looks bad if there is any space.
4. Cover the newly exposed roots and the portion of the stone that they are on with soil. I generally use a large pot, set the stone and tree on top so that they will be at the right height later. Then I add a cut 1-gallon container or ring of plastic to hold extra soil in place.
5. Let the tree grow for one growing season - generally this is enough time for the roots to get to the bottom of the container and establish themselves down there. Then remove the extra plastic and the soil covering the rock and roots. You may want to allow the tree to grow freely for another few years to get the roots to really grip and look interesting before you begin bonsai training. You should probably time the removal of the extra soil and plastic to a time when it isn't really hot or really cold so the the newly exposed roots don't get too shocked. You can remove just an inch at a time if you're concerned.
You can see a couple examples in this thread:
http://bonsainut.com/forums/showthread.php?7033-A-few-pine-seeds-6-years-later.
Good luck,
Eric