After hours of digging (never worked with ExpressionEngine before) I found out why it was not working in our setup (EE v2.8.1, Freeform Pro 4.1.7). Leaving this here for anybody else looking for the answer:
Go to CP > Admin > Security and Privacy > CAPTCHA Preferences. There you will find two input fields that were empty in the site I was working on: "Server Path to CAPTCHA Folder" and "Full URL to CAPTCHA Folder". Fill these out.
The last one should probably be "/images/captchas" and the first depends on your server. You can find the correct path using PHP's getcwd. It should look something like "/var/www/vhosts/[...]/public_html/images/captchas". This folder should be writable.
After that the Captcha finally showed up.
A few dead ends, to help redirect misguided searches:
- The "{captcha}" or "{freeform:captcha}" EE template code was not the issue
- CAPTCHA being disabled for logged in members was not the issue
- "Enable Membership CAPTCHA" was not the issue (I think this related to registering, which we don't use)