Extreme difficulty will become available after completing the game on Hard difficulty. So Extreme difficulty will and should be your third playthrough.
Extreme difficulty is very similar to Hard difficulty but with a slight difference, if you lose all of your lives you will not start all the beginning of the stage. Once you lose all of your lives you will be sent back to the main menu and have to start the entire game all over.
By now you should be have some idea on how avoid taking damage and how defeat the boss battles. Just take your time and make sure to collect every health item and 1up that you come across.
Here is a video showing all the boss fights with no damage.
Thanks to packattack04082 for the video!