Or is it just post-game? I've seen one before but it was in the main story.
He starts appearing after you learn about the evolution stones in the main story, but he still is random, in Hideyoshi's story got him on december of every year (20 years) but in Kenshin's he never appeared in 20 something years
So yes, they do. Source: http://www.gamefaqs.com/boards/654723-/63399484
They can come during the main game yes.
Source:I had a wigglytuff before I fought nobunaga which you can only get if you meet a merchant.