I won this game playing as Portugal on Monarch difficulty.
It is important to get Colonization as soon as possible. Also, try to grab Cuba if you can: it produces two (2) treasures, tobacco and sugar. Other than that all that I held were enough cities to cover the gold and gem mines in Africa. I only needed to found about 4 cities in Africa and the one in Cuba to win the game.
Try to time the building of your plantations/mines/etc. so that they pop out treasures right about the same time. This cuts down significantly on the transportation problems between the colonies and the capital.
For instance, I built a tobacco plantation in Cuba that produces a treasure every ten turns. I planned to build the sugar plantation so that it would pop out a treasure about the same time as the tobacco, so that I would have two treasures appear at the same time - that could both be loaded onto the same carrack, thus eliminating the need for another shipment. I did the same in Africa - all the cities there were producing treasure units around the same times (though gold seemed to come twice as fast). The result was that I often had a carrack arriving from Africa full of treasure instead of wasting a trip on just one. Set this system up and then just try to stay out of wars, cover the carracks with frigates, and the other civs simply cannot catch you as your score skyrockets you to victory.
Another thing to remember is to always make sure that your carracks are full of troops/units that can pick up the treasures and hop right back on the ships. I used knights as much as possible for this as they were quicker at shuttling between those backwater sub-Saharan African gold mines and the ships waiting on the coast.
Oh yeah and build Magellan's Voyage if you can.