Demanding a tribute makes it harder for the CS to fear you. It will give it something like 200 points which need to be surpassed by points generated by your military power (overall military power + military near the CS). This is decreased over time, until it is completely gone.
Other factors that give points to CS, and make it harder for the CS to fear you are: having negative influence, CS personality (a Hostile CS will have extra points), having a pledge of protection, and having an ally (I'm not sure about this one).
You can hover over the Demand screen and all information is displayed. With gunboat diplomacy you get a 50% bonus to your military power so it will be easier. If you are not influencing the CS, most of the times bringing around a couple more strong units is enough. Unless you are Greece, you need to be careful not to stay in CS territory (at least until you become friends), and also removing a pledge of protection will help.