I can start the song by pressing the P key but I can not stop the song being played. Logic Bricks are very confusing.
The reason that does not work is because of how the keyboard sensor works, it essentially is stopping and restarting the sound.
What you need to do is have a game property (A boolean set to true). The keyboard sensor is plugged into a Property actuator set to Toggle.
It is then that property that controls the sound actuator. Add a Property sensor, set its Value to "True", the Property to the game property created earlier, and leave the Evaluation type set to Equal.