After Columbus's voyage to the new world, how quickly did this knowledge spread into the other parts of the old world? For example, when did the existence of the new world was a "common knowledge" (in laypeople, or if that's too vague then in the rulers of various kingdoms) in various European countries, middle eastern civilizations, Indian subcontinent and China? If this is too broad or too vague, I'm particularly interested in the general awareness in Indian subcontinent.
Although the discovery of new routes was quickly published (as Tyler points out in his response), the first recorded descriptions of the lands as a "New World" was made by Americo Vespuccio in the beginning of the 1500s decade. It is to note that Vespuccio's orignal claims were only about the Brazil coast that he had explored.
But those were in private letters; I would said that knowledge was exposed to the (informed) public with the maps of Cosmographiae Introductio.
As for the other parts of the world, Portuguese stations in India would have been iformed pretty soon (if anything, to warn them of the possibility of the appearance of competitor ships), but I do not know how much information did the Portuguese share with the native Indians (my guess is that only the strictly necessary, in order to improve their commercial situation).
By March 1496 even the English had located and employed their own adventurers to explore the New World, namely John Cabot and Sons, by granting Letters Patent in exchange for a 20% Royal interest in profits:
For John Cabot and his Sons.
The King, to all to whom, etc. Greeting: Be it known and made manifest that we have given and granted as by these presents we give and grant, for us and our heirs, to our well beloved John Cabot, citizen of Venice, and to Lewis, Sebastian and Sancio, sons of the said John, and to the heirs and deputies of them, and of any one of them, full and free authority, faculty and power to sail to all parts, regions and coasts of the eastern, western and northern sea, under our banners, flags and ensigns, with five ships or vessels of whatsoever burden and quality they may be, and with so many and such mariners and men as they may wish to take with them in the said ships, at their own proper costs and charges, to find, discover and investigate whatsoever islands, countries, regions or provinces of heathens and infidels, in whatsoever part of the world placed, which before this time were unknown to all Christians.
It was known throughout Europe virtually instantly, meaning within weeks of Columbus' return to Barcelona on March 15, 1493, where he was received as a huge hero.
Not only did the knowledge of the New World become universal thoughout Europe immediately, but they immediately starting dividing it up, even though they had no idea of its dimensions! On May 4, 1493, less than 2 months after the first return, Pope Alexander issued the papal bull Inter Caetera ("Among Other Things") which stated what is now known as the Doctrine of Discovery.
Presumably, India would have learned of the discovery as soon as the first traders arrived bearing news from from Europe, which would have been in about 2 months after the return, so approximately early in June, 1493.