While that quote has been attributed to Twain (and several others) over the years, there is nothing to suggest that Twain used this particular phrasing nor was he the originator of it. That credit goes to George H Derby, under the pseudonym John Phoenix, back in 1855.

The trifecta of “kings, editors and people with tapeworm” has been widely attributed to Mark Twain, but like so many witticisms credited to him, there’s no record he ever said it. It’s also unlikely that Henry David Thoreau ever made the remark once ascribed to him: “We is used by royalty, editors, pregnant women and people who eat worms.”

Worms, or more specifically tapeworms, figure prominently in we-­related humor. The earliest known joke to combine parasites and pronouns comes from George Horatio Derby, a humorist from California who assumed the pen name John Phoenix. “I do not think I have a tapeworm,” he wrote in 1855, “therefore I have no claim whatever to call myself ‘we,’ and I shall by no means fall into that editorial absurdity.”

New York Times, Ben Zimmer, 2010-10-01