The Lake Nemi ships. These were two ships discovered in Lake Nemi and dated to the time of the Emperor Caligula. They were described as being floating palaces and a number of accounts state they had mosaics.
Here's a quote from the Wikipedia entry: 'The topside timbers were protected by paint and tarred wool with many surfaces decorated with marble, mosaics and gilded copper roof tiles.'
And also one from a history blog: The floors were paved with glass mosaic....'
They have pulled up some artifacts from the sites (the barges were excavated but destroyed by fire in 1944) but I wonder if they actually found tesserae?