From Diablo Wiki
- Place item you wish to alter into the Mystic's Enchant interface and a list of properties that you can reroll (replace) on that item will appear. Click the question mark next to both to see what properties they could reroll into.
- Once you have decided which property to reroll place the materials you need to give the Mystic for her to do so into the interface and hit Replace Property. This is the point the enchant is locked into place and the restrictions listed below come into play. Materials and gold are deducted at this point too.
- Select the replacement property from the list of available choices. It could be the original property to keep the item unchanged.
- Reroll the property if you aren't happy with it.
Scope and Restrictions
- The property you wish to change becomes locked in (forever) the moment you select it and hit Replace Property.
- The Mystic will also offer the original property you are trying to replace so if you don't like any of the new ones you can just keep the original stat. For the original cost in materials and gold.
- Only one property can be rerolled but it can be rerolled repeatedly, each time costing materials and increasingly higher amounts gold to do so.
- Enchanted items become bound to your account (BoA), even if you chose to not accept the new enchants and kept the original.
- If you do not accept an enchant and keep the original property that is still the only property you can try to reroll.
- It has not yet been decided if permanent properties on legendary items can be enchanted or just the random properties: 
Development of Enchanting
The first mention of "enchanting" came from the Caravan FAQ, released in August 2010 at the Gamescom expo. There was just a single line about the Mystic, which credited her with Enchanting, but didn't give any indication what that meant.
A quote from an interview with indiablo.com from Gamescom 2010 confirms that the bonuses are not random:
More information on Enchanting was revealed by Jay Wilson in an interview at Blizzcon 2010. 
From the way Jay describes "finding enchantments" it makes them sound like recipes. Recipes are what the Artisans use to craft new, semi-random items in Diablo III's form of gambling. Artisans know some recipes to start with, and acquire more through their level up training. But the best recipes in the game are found as drops from monsters. These recipe scrolls are then given to the appropriate Artisan, and from then on that Artisan can craft that item.
When asked what happens to her enchants Blizzard confirmed:
The Mystic's return was revealed at Gamescom 2013 although details of all her abilities were not revealed the fact she would be able to reroll an affix (enchant) was and welcomed by the majority of the community.
- Enchant Q & A - CM, Blizzard Entertainment, 13/11/13
- More Details on Enchanting - Blizzard Entertainment, 04/09/13
- Gamescom Interview - August, 2010
- Jay Wilson Interview Diablo3-esp.com, 21/11/2010
- The Fate of the Mystic's Enchants - Blizzard, 28/1/2012