How enthusiastically should I strip a flaking deck before staining?
Based on what I've seen in the pictures I'd say you have two option: 1) get a sander and sand the entire deck or 2) get two gallons of stain remover and spray in on the entire deck and scrape it all off. Deck stains are most durable when applied to wood and coating new stain over bare wood and then wood with old stain won't give you the results you want. 

Also, are you sure the stuff on the deck is stain? It sure looks like paint, especially the way it's peeling. I bring this up because most stain removers do not remove paint. I'd suggest taking a few samples of the "stain" flakes and bring it into a paint store like Sherwin Williams and getting their advise.