I know, I know, the platformer genre's been done to death. Yet I'm encouraging it.
But: I'm not encouraging making something derivative. There are plenty of unique spins
on this genre. And as with any genre, try looking at the history and standout examples of the genre. Many of them add puzzles, many are combat-focused. Some are 2D, others 3D.
That makes an important point - mixing and matching elements in unexpected ways,
is useful for finding something creative and different! Indeed, one could argue that recombination of existing stuff *is* creativity, and the trick is having the intuition to choose which combinations will be interesting and enjoyable and which won't.

Often getting a handle on genre possibilities involves, guess what, playing games.

So here are some outstanding modern examples of 'platformer design':
-"Psychonauts" has a great art style and many wildly creative ideas.
-"Portal" uses spatial manipulation in 3D very cleverly, as doe sthe 2011 sequel.
-"Fez" uses spatial compression very inventively as a mechanic.
-"Braid" does some really ingenious stuff with time manipulation.
-"The Bridge" uses gravity rotation mechanics inventively.
-'Mark of the Ninja" is a masterclass in stealth platformer design.
-"Super Meat Boy" is, unlike some others here, not puzzle-based but does some absolutely tense action stuff with unique abilities and obstacles.
"Mirror's Edge" takes inspiration from parkour in urban settings.
-"Darq" is a creepy and very recent indie platformer which also is very cool.
-'Journey' is also fantastic and beautifully designed and a great example of how to make a meaningful story work without words.

Once you've played games like these you'll realize just how wide the possibility space for this genre actually is once it's mixed with other ideas. Moreover, while GTA V cost $265 million to develop and had a development staff numbering over a thousand people, some of these titles listed above were made mostly/primarily by just one core person. (i.e. Braid, Fez, Darq)

As always, use a good flexible game engine that is actively supported and has a good sized community, and that will be around a while. I like Scirra's Construct 3 for 2D games [or the older C2 if you don't like subscriptions] and Unity for 3D but you can go with whatever makes sense to you. I certainly am aware that Unreal is very popular and for good reason, and Stencyl and GameMaker are pretty good for 2d right now. I don't like GameSalad, too many arbitrary restrictions, and there are lots of niche 3d engines that I likewise tried and ditched such as Torque. But these are just my opinions.

Structurally, it's wise to have a premise, a core idea that sums up the game - but that premise ought to have various uses and variants, assorted implications that interact in interesting ways. These are generally 'obstacles' for the player to get past, and types of 'skills' or abilities the player has, which make it possible to beat the obstacles. Common obstacles will involve jumping on platforms with different properties, thus the name of the genre - as well as enemies with varying behaviors, and sometimes puzzle elements which must be solved. (Check my article on puzzle design for more info on that)

Some platformers recently are procedurally generated so they can continue indefinitely {ie Temple Run, Doodle Jump, Canabalt, Alto's Adventure] and these are also described as 'endless runners'; others are carefully designed in a meticulous way by the developer. It's a programming challenge to make procedural design consistently work well, and it makes storytelling and a defined structure much harder to implement. The upside is the game has no defined end point.
But that's also a potential downside if you wish to tell a story. [See: Storytelling articles for more info. But know that story should be full of events actively initiated by the player and should not just be cutscenes the player passively watches for a long time - if that's what you want, you're making a movie, not a game. Games are defined as a medium by the active participation of a player [or multiple players]!]

So, find some cool mechanics, think of a mix of fun ways to use them. If you can only come up with one thing to do with an action, maybe it's not worth implementing, but try to find actions and movements that have multiple uses when combined or used in different contexts. Iterate and playtest. Do not do things the players will see as unfair. Make collision boundaries reasonable so the player doesn't miss jumps they should be able to make, or fail to hit enemies they should be able to hit. Collision bounds should match the objects convincingly, yet do so without being as highly detailed as the visible sprites or meshes. A super detailed collision setup in a large level will slow things down, and if there is resulting lag it makes the game way harder to play, which is a massive no-no in this genre and with anything where timing matters.

Find ways to innovate and combine elements in weird and imaginative ways. But don't assume every aspect of the game should be wildly 'out there' - this can confuse and alienate players.
Give them some familiar elements they can hold onto as a sort of framework for playing your game, but also twist things in some new directions as well. Too familiar and it's derivative, too unfamiliar and it's alienating and bewildering. Give players something in between the weird and normal. And make sure it starts with easy challenges and scales up in difficulty, introducing a greater challenge in each level until the end. [if there is one] to keep things fresh. If telling a story, break that into sub-steps or sub-objectives that naturally lead into the larger goal at the end. Irrelevant objectives which add little progress to the core goal, are sidequests and they tend to annoy players.

Otherwise... just experiment and try things, and if they are not working, change them or cut them out, better to streamline some un-fun or broken design stuff than leave it in the final game.
Ads on TriumphantArtists.com and other websites run by Matthew Hornbostel, include banner ads from Comic Ad Network [top ad - an unfiltered banner rotation system predominantly used by web comics, art sites, but occasionally some questionable items.] and my own banner rotation system [bottom - anything here is either my own stuff like websites, online shops, or social media profiles, or has been vetted by me and found to be generally legit. I have several cashback sites [all of them are ones I've used and cashed out tens of $ from successfully already] and major online retail stores [Sony, Microsoft, Amazon...] in that mix. Usually they give me some sort of small compensation if you buy from them through the link, which I'm disclosing right now. They're all legit spots, but if skeptical do your own research before committing to anything.]