You mention staining in your post title.

The darker the wood the less the spaces show. Plus as you add deck lines and bungees you'll be surprised how little these things that are bugging you will actually show. If you have a few really bad gaps you would fill it with the same wood as the deck. Take a strip and plane it thin with a sharp edge on one side and force it into the crack with tiny bit of glue. Once dry you can cut it flush and sand it. That will accept stain fine and be invisible.