Rumor Bosses appear randomly in the background, about 3% chance per hour of game play, per Rumor Boss type. That results in about 2 or 3 appearing per hour of game play, sometimes more.
Once a Rumor Boss spawns, you have a chance to here about it by Gossiping, but you don't need to hear about it to run into it (can make for an unexpected surprise). If a Rumor Boss hasn't spawned yet, NO AMOUNT OF GOSSIPING WILL MAKE ONE SPAWN.
One of the better ways to hunt Rumor Bosses is to work on Town Hall Quests or spam an dungoen for XP. As you rest (or gossip for Town Hall Quest hints), you'll pick up leads on the Rumor Boss once one (or more) spawn.
Remember, the 12 shards are supposed to be a long quest that you knock out in parts while working on the other quests.