A few ideas:

- Use music theory to minimize accidentals (as proposed here)
- This seems to work about 90% of the time

- Use music theory to maximize non-accidentals
- Use music theory to maximize non-accidentals weighted by their prominence in the key (e.g., I weighted highest, IV and V weighted next-highest)
- Learn weights from data

- Use music theory to minimize accidentals weighted by their prominence in the key (e.g., bVII weighted lowest, bVI weighted higher)
- Learn weights from data

- Use music theory to minimize accidentals to get candidates and then use music theory to choose intelligently from candidates
- Use music theory to maximize non-accidentals to get candidates and then use music theory to choose intelligently from candidates
- Use neural network
- Use HMM

Interesting ear training and other techniques and sites:

- Forum about this exact question
- Lesson on key from chord progressions which uses the music theory to minimize accidentals
- Wikihow focuses on key signature, humming, and just practicing]

It's crazy how everyone essentially agrees there is a way to do it, but it always comes down to how it “feels”; is it “finished”? Where it “lands”. And other ambiguous phrases.