Colonia del Sacramento (Nova Colonia do Santissimo Sacramento) was founded in 1680 by the Portuguese (Manuel Lobo), sandwiched in between the Portuguese colony of Brazil and the Spanish Vice Royalty of the River Plate (later Argentina, Uruguay and Southern Brazil). Its strategic position and use as a smuggling port meant that its sovereignty was hotly contested and the city changed hands several times between Spain and Portugal.
Two daily boat connections arrive and depart from Buenos Aires and are the main connection to Argentina. A fast expensive one and a cheap slow one. The fast Buquebus  catamaran ferry (one hour) costs around 70 USD return (when booked in advance) and around 110 USD when booked the day prior and is usually quite crowded with day tourists and travel groups. Of of the fast boats have free wireless internet (WiFi, satellite link) Make sure you book in advance for weekends and the peak season (Christmas until the end of February). The slower boat costs 102 Pesos (from Buenos Aires) round trip, and takes about 3 hours. Note that although you are traveling North-South, the time in Colonia is 1 hour ahead of Buenos Aires, so it is important to reset your watch (especially if you don't want to miss your boat on the way back).
A cheaper possibility is to take a boat from Tigre to Carmelo in Uruguay. From Carmelo, take a bus, which run every two to three hours from the center of the city to Colonia. Great landscape and also drops off kids from school along the way.
There are several connections by bus from Montevideo to Colonia, with most buses leaving from Montevideo's Tres Cruces terminal . The ride takes 2.5 to 3.5 hours depending on stops and costs about UYU200 pesos. Be careful with people telling you that all buses are booked out. This is in general not true and a taxi is much more expensive. For the peace of your mind buy a bus ticket upfront to avoid rare disappointment.
Colonia is a good for visa runs for those people who wish to extend their stays in Argentina.
The old city of Colonia, which holds the main attractions, is quite small. It can be easily walked in a single day. There are shops where you can rent bicycles or scooters which you can use to ride around the city or in to the countryside. Streets aren't always in perfect condition, so keep an eye on the road, especially cobbled ones.
The ferry terminal is about half a kilometre south of the old city and the main bus terminal is about a kilometre south of the city center.
You can rent row and sail boats from the marina.
The main attraction of Colonia is its historic center. Seven small museums in the center can be visited with only one cheap entrance ticket, which must be purchased in the Museo Municipal. For a few pesos you can go up to the top of the lighthouse (faro) and see most of the city and look out over the city and the river.
Outside of the city there is a semi-abandoned amusement park with Uruguay's only bullfighting ring, no longer in use.
There is a large tourist information center adjacent to the ferry terminal, and a small office at the western terminus of Calle Manuel Lobo.
The old city is full of restaurants which serve the weekend tourist crowd from Buenos Aires. The specialties are Italian and asado (barbeque).
Colonia was also settled by Swiss immigrants and is home to a unique local Swiss cheese that you can get at the markets.
Yerba mate, the local drink of choice. Every single person here carries around their own cup and bombilla, so when in Rome...
Colonia is a preserved tourist town with very little of the harassment seen in most cities in Latin America. The dominance of local weekenders from Buenos Aires and Montevideo creates a very different environment from other tourist cities.