Please don't bake the rocks! Some can have trapped air pockets and in an oven this air can expand breaking the rock apart with force!
Boiling's probably OK, but perhaps just pouring boiling water over them a few times is just as good. A clean with a brush and then another soak with boiling water should be plenty to clean it.
A few more considerations are the type of rock/stone. It should be very a hard rock, granite, quartz or slate, for example, one that won't dissolve and inadvertently change the water chemistry. As Derp suggests, the vinegar test is a good start. Try to avoid ones that crumble easily in your hands or appear to be chalky.