I don't know if Twain was talking about the Cardiff Giant when he wrote
"Petrified Giant," but the Cardiff Giant is a wonderful story and might
have inspired Twain.
A man in the area (can't put my hands on the particulars right now) had
a "petrified man" built of gypsum, treated, and interred for a period of
time on a Cardiff farmer's property.  The farmer, in on the hoax, was to
sink a well and "discover" the amazing giant.
When it was unearthed, scholars and scientist flocked to Cardiff to
study it.  Some said it was a genuine petrified man of giant
proportions, others said it was a fake.  The perpetrator advertised it
as genuine, and people came from all over to see it, paying quite a
large sum to view it.  It was at the Famer's Museum in Cooperstown when
I first saw it in 1959, displayed in the ground as it was found.
It eventually went "on the road" and ended up on Broadway in NYC where
the curious were happy to part with their money to see it.  P.T. Barnum
had a museum in N.Y.C. at that time and wanted to buy the "giant,"
whatever it was.  The owner refused to sell, so Barnum thought about how
one would construct such a "petrified man" if it was indeed
constructed.  He arrived at the same conclusion as the original builder
and built his own Cardiff Giant, the "real one," he claimed.  He said
the one exhibited down the street was a fake!  Both giants played to big
crowds.  I came upon Barnum's giant, standing, in the Barnum exhibit at
old the Danbury Fair before it became a shopping mall.  I later saw it
at the Barnum Museum in Bridgeport, CT.  It was, in fact, a dead ringer
for the Cardiff Giant.
We know Twain visited the Barnum Museum in NYC because he wrote about it
(and dismissed it and its "dried up frogs in glass cases"), so he may
have seen it there.  Or, as Dr. Dalrymple pointed out, he might have
seen it in Cardiff when he was in Elmira.
I moved away from the east 23 years agp, so I don't know the fate of
either giant since I left.  Easy to find out though by contacting
Farmer's Museum or City of Bridgeport, CT (they used to have a Barnum
Festival in the summer to honor its most famous resident).
I'm sure you'll have many replies on this.

Elinor Reiss
San Diego, CA