They did at least reach southeast India as early as in the 1st century, as is proven by coins and pottery and some buildings (amphi-theatre). http://news.bbc.co.uk/2/hi/south_asia/4970452.stm Pepper was imported form south India since this time and is found in excavations in roman castles in Europe. Some nice coin pictures are at the wiki page: http://en.wikipedia.org/wiki/Roman_trade_with_India

This is a question with quite a bit of heft to it, so I will try to be more or less brief and basic, and if there are any follow up question I am happy to take them.

First off, they did! I can't seem to find the exact passage, but there is one Chinese chronicle that described a Roman embassy to the court that was picked up in Fu-Nan (Vietnam). However, the items they had to offer were all local to the region where they were found, to the disappointment if the Chinese who were reasonably expecting something more lavish and exotic, and thus it has been interpreted that these were actually Roman merchants who were trading in the area of Vietnam, were picked up by the Han military contingent there, and pretended to be ambassadors because they assumed it would be safer. There is no mention of a follow up delegation and so some have suggested that the Antonine Plague, which reached Alexandria the very next year, essentially destroyed the Indian Ocean trade, although a century later Roman merchants are mentioned in the region so there may have been another that simply went unmentioned in the turmoil of the Han Dynasty at the time.

But that is the end of the chain, where is the rest? I personally think your instincts are correct, and that the image of camel caravans crossing Eurasia baring silk and spices is one that fundamentally belongs to a later period. Certainly, some material did move in this way, as archaeological evidence from Western China has confirmed, but I and most scholars of the subject have begun to feel that the Indian Ocean was the more significant route at the time. At the moment, the contours of the trade routes are quite well understood for the Western Indian Ocean but not for the Eastern and the Bay of Bengal--the sad fact is that the archaeological record weakens the farther east you go simple because of the focuses of research. I am optimistic that this will be much better within ten years, particularly as the scope of SE Asian archaeology has been broadening beyond the traditional focuses on the ethnic based expansions and classical Empires, and as archaeology in southern China begins to come into its own, so ask again in a decade. That being said, there has been a recent argument placing the southwest Silk Road through Yunnan at the fore, so that should be thought of as a major route.

Moving to Rome, there were two routes from the Indian Ocean to the Mediterranean: by far the most studied and probably the most important was the route through the Red Sea to Egypt, then up the Nile to Alexandria. The Eastern Desert between the Nile and Red Sea is a pretty inhospitable environment, but the trade seems to have been so vibrant and important that a series of rather vibrant port cities developed. From there, they could sail down the Red Sea and catch the monsoon winds from the mouth direct to the Indian coast, with no shore hugging needed: I gave a fairly detailed description in this post, if you want more information. The second route was through the Persian Gulf, up the Euphrates, then across the desert to Syria. It was once thought that this was disfavored because of tensions between Rome and Parthia, but that probably isn't correct and implies a sort of trade competition between the two that probably did not exist. Some recent research has shown that the different schedules of these two routes, based on oceanic wind patterns and the flow of the river, probably reached the Mediterranean about six months apart from each other, so they were more complementary than in competition.

These two routes converged in India, where for some time there had been a complex network of coastal and overland routes crisscrossing the subcontinent. The first century also sees the development of Sri Lanka as a real lynchpin holding the oceanic commerce together, but unfortunately the relevant excavations at Mantai (near Mannar) which could have told us so much were forced to halt in the late eighties after a single season due to civil war. Other research on the island, however, has told us a great deal about Indian trade of the period, which was extremely vibrant and had a great deal of time depth.

So the commerce in the Indian Ocean, which ultimately connected Rome and China and was anchored on India, was extraordinarily complex, likely much more so then even people thirty years would have believed. There is a lot of uncertainty, particularly as you move farther and farther east, but it is a fascinating and very fertile area of study, and one that has a great deal of potential to change how we envision Afro-Eurasian history and its connections.

The best source from a Roman angle is Gary K. Young's Rome's Trade with the East, which more than ten years on is still a fantastic introductory text and overview. He necessarily peters out a bit farther east, and Bin Yang's Between Wind and Clouds presents an excellent perspective from Yunnan, and Berenice Bellina and Ian Glover's relevant article in Southeast Asia: From Prehistory to History gives a good overview of that region's place in the topic.

They did, and it was probably more common. The Periplus of the Erythrean Sea gives a great deal of detail on travel through the Red Sea and Indian Ocean.

That said, there's a difference between mercantile transactions on an annual basis and sustained diplomatic ties, let alone elite interaction and intermingling.