I’m not trying to steer you away from your goal, lord knows we all want Megaman’s spirit to live on, even if Capcom doesn’t.
That said, Basil is right about starting small. You could go two ways with it, make the classics such as pong, tic-tac-toe, tetris and more. Or you can make small prototypes that flesh out parts of the game you dream about creating.
If Java is your first attempt at making games, be ready for a long road. Sauron’s recommendations are good ones once you have the basics of Java under your belt. I myself wish I would have gone that route earlier. Still using Java2D for my games and I’m starting to feel the limitations(Could just be bad programming too though).
Now here’s some of the tutorials I’ve watched, coded and recoded and broke, until I understood them.
I want to make it a point that anything you learn from these is not only way to go about things. They’re just a starting point. As you make games and mistakes you’ll gradually find what works and does not(Mistakes are wonderful, if you’re not making mistakes, you’re not making progress.)
Math for Game Developers
Wonderful lessons here that you will find useful no matter what you use to make your games.
Game Programming with Cherno
Not the first series I learned from, but you’ll pick up some knowledge along the way.
Game Programming with Zephyr
This series takes you along creating a minimal copy of Notch’s Ludum Dare entry ‘Minicraft’. Towards the end, you’ll get to explore the joys of implementing Multiplayer.
Java platformer Tutorial
This one will probably interest you the most, since it’s in the same genre of Megaman.
I probably don’t have to say this, but type the code along with them. If they supply source, only refer to it if you can’t figure out what you’ve done wrong(usually it’s a mistyped variable). If they don’t explain something thoroughly enough for you, research the concept or classes they use(A lot of tutorials don’t explain the why’s quite often).
That’s all I can think of for now on the programming side of things.
Good luck with your programming adventures.