In 1861 Our Little Paper of Lansingburgh reprinted a recipe for a coffee substitute possibly taken from the American Agriculturalist magazine, as the latter credited it to a reader while the former (otherwise verbatim) did not. The Troy Daily Whig also published a similar recipe.

Sweet Potato Coffee.
Mrs. Ann Hoopes, Vermilion Co., Ill, writes that a very good substitute for coffee can be made from sweet potatoes. Wash and scrape good sound tubers; cut them into pieces, half an inch long; dry them in the stove; roast them as you would coffee, until of a light brown color. Make “coffee” from them in the usual manner, except that the pieces are not to be ground.
American Agriculturalist for the Farm, Garden, and Household 20(4). April 1861. 119.

Sweet potato coffee is out. Sweet potatoes, cut into pieces the size of coffee grains, roasted in a slow oven for the same length of time that coffee is, and then mixed with an equal amount of coffee, will it is asserted, produce a beverage fully as palatable as the genuine and original article.
Troy Daily Whig. December 16, 1862: 2 col 4.

Alternatives thrived during the Civil War; e.g. “Confederate Coffee Substitutes: Articles from Civil War Newspapers” documents versions made from okra seeds, persimmons, caramelized molasses, beets, asparagus, parsnips, acorns, chicory, corn meal, rye, field peas, cotton seed, etc.!

For much of the war, the massive Union Army of the Potomac made up the second-largest population center in the Confederacy, and each morning this sprawling city became a coffee factory. First, as another diarist noted, “little campfires, rapidly increasing to hundreds in number, would shoot up along the hills and plains.” Then the encampment buzzed with the sound of thousands of grinders simultaneously crushing beans. Soon tens of thousands of muckets gurgled with fresh brew.
Confederates were not so lucky. The Union blockade kept most coffee out of seceded territory. One British observer noted that the loss of coffee “afflicts the Confederates even more than the loss of spirits,” while an Alabama nurse joked that the fierce craving for caffeine would, somehow, be the Union’s “means of subjugating us.” When coffee was available, captured or smuggled or traded with Union troops during casual cease-fires, Confederates wrote rhapsodically about their first sip.
Grinspan. “How Coffee Fueled the Civil War.” New York Times. July 9, 2014. Blog.

Substitutes were not entirely the product of scarcity in the South due to the Civil War, however. Lansingburgh and Troy papers published some in the several years just prior to the Civil War:

Cheap and Valuable Substitute for Coffee.

The flour of rye, and yellow potatoes, are found an excellent substitute for coffee. Boil, peel, and mash the potatoes, and then mix with the meal into a cake, which is to be dried in an oven, and afterwards reduced to a powder, which will make a beverage very similar to coffee in its taste, as well as in other properties, and not in the least detrimental to health.
Lansingburgh Democrat. July 28, 1860: 1 col 1.

COFFEE.—Peas, wheat and carrots are each a good substitute for the coffee berry. Peas will be found to differ hardly at all in the taste, while wheat is often preferred. Carrots mix very agreeably. One-half real coffee and one-half peas, burnt to a nice cinnamon brown, will perhaps be the best for a first experiment in this economy.
Troy Weekly Times. March 14, 1857: 1857: 2 col 3.

Coffee substitutes can even be found decades earlier. Some of the things proposed as coffee substitutes are still imbibed today, but would be far more likely to now be called herbal teas or infusions.

It is said that the French, since they have been prevented from importing colonial produce, have discovered a substitute for coffee, in the roots of endive, or what is more generally called dandelion.
Expositor [Geneva, NY]. June 22, 1808: 2 col 2.

Parsips […] are the best substitute for coffee and chocolate. For that use they must be cut, dried and parched; they require no sweetening.
Geneva Gazette. June 4, 1817: 2 col 2.

Substitute for Coffee — The Baltimore Morning Chronicle mentions, that a merchant of Philadelphia retails forty bushels of roasted rye per week, as a substitute for Coffee. The Chronicle adds—”Rye Coffee is much used in Baltimore already, and we have no doubt that the more generally it is known, the more the substitute will be adopted; and economy of this kind, and at this time, deserves to be patronized by every patriot.”
Freeman’s Journal [Cooperstown, NY]. February 28, 1820: 3 col 3.