That is paint. And that is paint with no primer applied.
That is good news for you as you don't like the color. It is bad news for your deck, as it has probably logged a lot of water.
The easiest way to remove this is roll on some paint stripper and get a power washer going. You are going to have to access how each board looks after you can see it better and replace anything showing signs of rotting.
Can you stain pressure treated wood (pine)? Yeah... but you are going to have to try some things out and make sure you are happy. The cheapo pressure treated big box lumber from experience does not hold stain great.
However you have an edge because you want it darker and a darker stain might hide the imperfections and hold better. You are going to have to try some sample of stain and just hit small parts of your deck - I would do the decking or tops of railings to test.