So I never thought that the history of computing would ever intersect with Abraham Lincoln. For this reason, and this reason alone, I felt I needed to answer this question. Because my answer exceeds Reddit's character count, this is a three-part response.

Admittedly, I know much more about the history of computing than I do about Abraham Lincoln. While I cannot speak to the veracity of Lincoln's anecdote (e.g., did he actually say what Doris Goodwin claims he said), I can speak about the questions at large, which seem to be (1) could 19th century technology be used to create a chess-playing computer, (2) what technology would Abraham Lincoln have been anecdotally referring to (if the anecdote were in fact his), and (3) could Abraham Lincoln actually have been an eye-witness to a 19th century chess playing automaton?

The answer to the first question is theoretically yes, but practically no. The answer to the second question is that the anecdote was probably referring to something known as the "Mechanical Turk," a travelling exhibition popular in Europe and North America in the late eighteenth century and first half of the nineteenth century. The answer to the third question is that it's possible/plausible that Abraham Lincoln was an eye-witness to a 19th century chess-playing automaton like the Mechanical Turk, or at the very least heard descriptions of eye-witnesses. If the summary intrigues you, please read on:

(1) Could 19th Century Technology Create a Chess Playing Computer?

For a little background, up until the 1900's, anyone performing mathematical computations used precomputed tables of logarithmic and trigonometric functions in order to perform their computations (compared to doing the arithmetic by hand). This made life easier for anyone doing math, as they could refer to a pre-computed table for the value they needed for a particular logarithmic or trigonometric function (e.g., what is the value of the sine for an angle of 57 degrees?). These tables were particularly important to contemporary militaries for calculating predicted trajectories of cannon fire. Unfortunately, these reference tables were calculated by hand, which meant they often contained incorrect values.

The English mathematician Charles Babbage was particularly upset by the fact that he had to rely on such tables and that the tables often contained errors, which impacted the accuracy of his own work. Accordingly, he conceived of the idea of a mechanical calculator that could accurately and reliably compute these mathematical values, which could then be printed by the machine in a table. The British government, being immensely interested in being able to cheaply and reliably produce accurate trigonometric tables for the army and the navy, funded Charles Babbage's research into the manufacturing of his mechanical calculator, which is known to computer history as the Difference Engine. Accordingly, the British government began funding Babbage's research in 1823 (and abandoned it in 1842).

Charles Babbage was not alone in his pursuits. Others at the time also conceived of and researched various versions mechanical calculators. However, what makes Charles Babbage important to this answer is that during his work on the Difference Engine, he realized that the design for the Difference Engine could be generalized from a special purpose machine that computed answers for specific functions (i.e., an application specific computer) to a general purpose computer that could compute the result for any function.

As a result of this insight, Charles Babbage began designing the Analytical Engine in ~1833. The Analytical Engine is recognized today as the first turing-complete programmable computer - the mechanical equivalent of that laptop or phone you use to cruise Reddit! The Analytical Engine was a marvelous design of mechanical engineering. Babbage's assistant, Lady Ada Lovelace, was among the first (if not the first) to realize that because the Analytical Engine could compute the answer to any mathematical function, it could manipulate any data that could be expressed or represented using numbers. For example, Lady Lovelace wrote in 1843 that the Analytical Engine could be used to generate music or manipulate anything that could be symbolically represented as a number, which is the foundational insight of modern computing.

Unfortunately, the Analytical Engine was never built, although portions were assembled before and after Babbage's death in later years. The Analytical Engine was not built for a number of reasons. First, construction would have been incredibly complicated costly. Second, Babbage had a reputation for being difficult to work with and for failing to understand the needs of his benefactors.

Moreover, the Analytical Engine, if built, would have been slow. For example, Babbage predicted that the Analytical Engine could have multiplied two numbers, each twenty (20) digits long, in about three minutes. While that's faster than most people could accurately and reliably multiply twenty digit numbers by hand with pen and paper, it would still have been too slow to play chess. This is because most chess programs calculate all possible combinations of moves 3, 4, or even 10 or 12 moves out, and then choose the move that leads to the predicted "best" combination. This process is then repeated each time the computer has a turn. The Analytical Engine, while it could have been programmed to play chess, simply could not have performed the computations fast enough to be a playable opponent.

In summary, there was a design for a general purpose, programmable computer in the first half of the nineteenth century. Being Turing complete, it could have been programmed to play chess. However, it was never built. And if it had been built, it would have been too slow to actually play chess in any meaningful way. So while it would be theoretically possible (and probably a good steam-punk story), Abraham Lincoln could not have possibly seen a chess-playing "computer" in his youth, at least in the modern sense of how we understand the term.