Yes, there are archaeological finds of pottery belonging to the Tana tradition (a.k.a. triangular incised ware) in Lamu, Pemba, Zanzibar, Comoros and northern Madagascar.^1
Beyond this, there are the remains of the port of Mahilaka which arose in the 10th century and flourished until the 15th.^2 In many ways, Mahilaka resembles other port cities of the Swahili coast. Elite residents had access to imported glas beads, brass, Sgraffito pottery from the middle east, and Chinese glazed wares.
Further south is Andranosoa, another site bearing imported Chinese and Persian pottery.
We also have surviving oral traditions from the muslim Zafiraminia people of south-eastern Madagascar, as well as the Zafikazimambo that their ancestors immigrated to the island^3, most probably in the 12th or 13th century.
What sort of ships did they use? Most likely it was the arab dhow that was the backbone of commerce in East Africa in this time period. On the other hand, Ibn al-Mujawir's Tarikh al-Mustabsir contains mention of a trade route connecting Aden-Mogadishu-Kilwa-Madagascar. Neville Chittick has concluded that Ibn al-Mujawir's description of boats from Madagascar describes a vessel with outriggers. ^2 Of course, the Tarikh al-Mustabsir is an account of Ibn al-Mujawir's travel to the Arab peninsula from the east, most likely from Khorasan. So, Ibn al-Mujawir's account of trade routes and boats in the Indian ocean is second hand, and should be treated with some skepticism.
1 African Archaeology 3rd edition, by D.W. Phillipson, copyright 2005. pp 288
2 Oxford handbook of African Archaeology chapter 65 "madagascar" by Chantal Radimilahy
3 http://www.mohamedrabeea.com/books/book1_357.pdf pdf warning.
4 Cambridge History of Africa volume 3 Chapter 5, pp219.