It was a tad nerve racking at first, but we had our college friend show us the ropes on the first few trips --- she held out her hand, and quickly several cars would line up -- she told us to:

Scan the car, get a feel for the person.
Only tell them the address and ask how much.
Negotiate up from 100 RUB and typically settle around 200.

She gave us all of the phrases translated from Russian Cyrillic so that we could "recite" them effectively. We even negotiated one fare with an "official" taxi.

The speed at which these guys drove was a bit sketchy, and it was snowing on one of these days, but we rolled with the punches.