I happened to walk the southernmost part of this last month, as it follows the Ecovia do Littoral (a cycle-path also usable by walkers) along the coast. The Caminho seems to be marked not just from the town of Tavira, but from the W border of Tavira council. If anything, it is overmarked. It leaves the Ecovia in Altura, heading north (and I also saw markings where it passes Castro Marim train station).
The Ecovia is largely off-road, but I believe the bulk of the Caminho heading north through E Portugal just follows the main roads. There is some info on the route at
https://walkingbaesurissantiago.blogspot.co.uk/2015/12/2015-etapas-o-caminho-de-santiago-do.html.
The Ecovia itself starts at Cape St Vincent, and roughly follows the S coast eastwards through the Algarve, so if you like you could start anywhere on the coast, such as Faro, and join up with the Caminho further east. Its marking is a bit patchy, though, and it's not officially open yet (I assume the government ran out of money).