I've done more digging, and this is what I've found:
Paint
- Sits on top of the wood and is capable of forming a sheen
- Is good at keeping moisture out, but traps whatever moisture that does get in
- Should be easier to clean food / drink spills off
Stain
- Can't be applied over a previously painted surface (not a problem in my case).
- Bonds to the wood more closely than paint because it actually soaks in
- Allows moisture to leave the wood.
- Does not form a sheen - leaves original texture of the wood exposed
In my application, I chose to go with paint. I applied two coats of exterior paint with "built in" primer.
UPDATE
The solid stain lasted for a few years, but when I took off the table to expand the deck, I wasn't happy with how the wood was weathering so I replaced the boards with composite and was very happy except for the composite boards were incredibly slippery and had to be perfectly flat in order for your cell phone not to slide off.