I've been transcribing the journals of Alf Doten, a journalist who earned his living with the great Comstock Mining District's (and other elsewhere in Nevada) newspapers from 1864 throughout the rest of the century. Although he was working as a journalist in 1865, he doesn't mention any April Fool's activity for that year. In 1866, however, he posted the following for April 1:

April Fool day – I had an item in the paper this morning to the effect that a big cinnamon she bear & 3 cubs were captured near the Sink Carson & were in little house rear of Piper’s saloon – brought to town last evening & en route for California tomorrow – over 500 people called during the day at Piper’s to “see the bear” – big old sell – lots of fun

That said, this was hardly the beginning of hoaxing for Comstock newspapers. Samuel Clemens began working for the local Territorial Enterprise in September 1862 and continued there until May of 1864, taking his penname "Mark Twain" in late February 1863. One of his earliest articles was a hoax that failed miserably: he wrote an article about the head of a family in a nearby community who massacred his wife and children and then killed himself with a hatchet. Clemens believed he had placed sufficient clues in the article so that a careful reading would betray it as a hoax, but the article was picked up by many other newspapers, who published the account as fact and many readers - local and regional took it on face value. When the region learned that it wasn't true, Clemens came under considerable criticism; area newspapers denounced him, and the incident almost ended his writing career.

The problem with a hoax - like an April Fool's joke - is that it is effective only if there was a way for it to be unfolded (or if it is sufficiently harmless). A simple lie is not a joke nor is it an effective hoax. Another Comstock journalist, recalling his days working in the mining district, described how everyone there enjoyed practical jokes, but he explained that there were boundaries, asserting that "we never did anything worse than break a man's leg." Of course, he was exaggerating, but the point is well taken: there is a fine line that separates an effective joke/hoax from a lie or a cruel act.

Clemens/Twain honed his skills at the Territorial Enterprise, but he did not act alone. He had peers who were excellent journalists, writers who could provide examples of how to finesse a good hoax. Among them was his friend and sometime roommate, William Wright/Dan De Quille. De Quille was famous for his journalistic hoaxes, and no doubt he helped Clemens, the newcomer, learn how to avoid the disaster represented by one of his initial foray into the genre of journalistic humor.

The tricky thing about comedy is that it is funniest the closer that it rests near that fine line. We can all think of at least one comedian who "crossed the line" and apparently ruined a career (Kathy Griffin). Ultimately that happened to Twain on the Comstock. In May of 1864, he wrote a column for the paper about the local women who were volunteering for the Sanitary Commission - a Civil-War-era precursor of the Red Cross - which attempted to deal with the tens of thousands of wounded soldiers. Twain maintaining that the women (many wives of notable local men) were using the organization to advocate marriage between the races.

Twain maintained that he meant it as a joke, and more importantly, he insisted that he never meant it to be published, but that the newspaper printer grabbed the copy, set the type, and put it into the paper without Twain's permission. Regardless of what happened behind the scenes (no one is sure), several men were angry enough to make it clear that they wanted to kill Twain and there were threats of calling out the journalist for a duel.

Twain sloped away to use a term of the time: that is, he skeedadled and made his way to San Francisco, where he was able to continue his career, refining it as he went.

Twain returned to the Comstock in 1866 to give a lecture, and at that point, it appears that he was forgiven for the most part, but this serves as an example of how easily a journalistic hoax can go wrong.

My answer is only partially about April Fools, but with these examples, it is easy to see how any journalistic hoaxes can easily go wrong. These sorts of articles, whether associated with April 1 or not, could indeed cause problems.

As for when newspapers first started printing these things, I hope someone else can answer that part of your question. The Comstock was notorious for its hoaxes - one can argue that it is part of Western culture to exaggerate to the point of absurdity. Whether or not the assertion that it is unique to the region is fair, it is clear that it was part of the Comstock's journalistic fabric.