Checkbox
Advantages
- Will never be indeterminate. This is useful for coding, mostly.
- Can be represented in different ways. You can use 0, 1, true, and false. This reduces import errors, and simplifies report criteria.
- Is a true Boolean. This means formulas don't need ISPICKVAL to work, so they are simpler to read. This is also true in code.
- Requires only one click to toggle. Fewer clicks improves UX.
Disadvantages
- Cannot be indeterminate. This is a drawback when trying to represent data that may be unknown.
- Can't be changed to other data types later without data loss.
Picklist
Advantages
- Can be easier to read. A checkbox always shows a graphic image in reports instead of text. Unlike checkboxes, you'll get a friendly yes or no instead of an image.
- Can represent unknown values. Data isn't always initially available, so having an indeterminate value can be useful.
- Can present either option on top.
Disadvantages
- Requires translation for every language your org uses. Very cumbersome for multilingual apps on the app exchange.
- Complicates formulas with ISPICKVAL and so on. Makes Apex Code slightly more verbose. Also lends itself to coding errors.
- UX suffers. At least two clicks and an extra mouse move per selection.
Summary
In general, use a checkbox when possible for a better UX and easier maintenance. However, do use a picklist when you expect answers to be unknown from time to time.
Examples
Is driver insured? [yes/no]
Error Present [checkbox]
Over 18? [yes/no]
Requires Approval [checkbox]
The examples go on and on. In general, if you need to present an option that requires research, and might not be immediately known, use a picklist.
If an answer is always known (or, at least, should always be known), use a checkbox.