Fisher's test takes the row and column totals as fixed and asks: if the two variables were unrelated, how likely is a table at least as extreme as the one observed? With the margins fixed, one cell determines the rest, and its probability follows the hypergeometric distribution, so no large-sample approximation is needed.
Ronald Fisher's own example, from The Design of Experiments (1935), is the lady tasting tea. A colleague, Muriel Bristol, claimed she could tell whether milk was poured before or after the tea. She is given 8 cups, 4 of each kind, and told to pick the 4 milk-first cups. There are C(8, 4) = 70 ways to choose 4 cups, so picking all 4 correctly by guessing has probability 1/70 ≈ 0.014, which is the one-sided p-value.
Follow-ups: because the p-value can only take a few discrete values, the test is conservative, rejecting less often than α; Barnard's test is a more powerful alternative for 2 × 2 tables; the Fisher-Freeman-Halton test extends it to larger tables; and with large counts the chi-square test gives nearly the same answer much faster.