EDIT: Gah, just noticed you were interested in Sonic the Hedgehog style games. If that's the case, I'd heartily reccommend:
http://sfghq.emulationzone.org/Sonic Fangames HQ - Basically a big load of sprites, games, tutorials etc all making use of Clickteam (And other) game creation methods based around Sonic the Hedgehog. T'was where I started
(THat and STOS Text Adventures but that hardly counts)
Depends on how complicated you want to go:
If you're up for making 2D games with a kind of Drag-and-Drop sort of deal, various things I can recommend are anything from Clickteam (There's plenty of sites with various templates, examples etc available), you could try progging simple games in Flash (Like half the internet :p Occasionally a decent attempt does show up), Dark Basic and Torque are possibilities, but if you want to release anything with Torque you'll be handing over monies.
Failing that, You can go the coding route - C/C#/C++ and what have you. Ideally? I'd recommend a book (Which are often pricey). Failing a book, the Internet is a close second if you know where to find tutorials. GameDev's a good site for all round articles on game making, though many of them are a bit advanced.
There''s thousands of engines out there, many are free to use with limited licensing, one I've used is OGRE, which is geared towards 3D but can also manage 2D with no problems... Failing that you could just mess around in OpenGL until everything works (nehe.gamedev.com is a good place to start with that)
I second Clickteam's stuff is great for PIxel Art & Animation. Simplest editor ever but works fine and allows sprite animation to easily be classified (Stopped, Walking, Running, Jumping etc). Coding is done by scripting simple conditions with simple menus (if Bullet collides with Man, Destroy Man, Create Explosion, add 500 points etc.)
With Story? Sure you can read through various sites and what not on how to right a good story but often the best tract is simply to read lots of books, comics, stories, short or otherwise. Play games, see how the story progresses, how characters are introduced, how dialogue is written etc.) Also, try writing your own
THe tricky part is avoid directly copying anything that comes before, but make no mistake chances are you'll probably subconsciously borrow from your favourite stories and that's more or less ok - Just make sure your version still comes across as fresh.
Gameplay comes into a thousand and one different categories. Obviously, don't make a FPS :p Aquaria takes the best elements from Castlevania/Metroid and Ecco the Dolphin and blends them expertly, and that's often where the best games shine. Take elements you loved from your favourite games and combine them, but don't go insane. If you *do* want to come up with something truely original you're in for a harder time (We're talking a "define your own genre" here) - My advice is to do what many games in the Indie field do: Go back to retro concepts that made gaming simple, fun and addictive and try your own hand at it. 2d PLatformers and Scrolling Shoot-em-ups are quite popular these days
If all else fails, go back even further and do what everyone's doing these days and remake Snake, Asteroids or Pong
