I strongly recommend watching the AH or checking out the goldsmithing guild in Mhuara.
As far as growing them, I believe
Cactus Stems give you the best chance at seeing a colored rock, but keep in mind that not all of these recipes are 100% accurate. Fruit seeds also have a decent chance as well, I think.
I'd link you pikko's site, but I don't know the url nor do I know if it's still up.