I build as I go. Full on. Generally I start with a thematic idea in my head and have some idea what 'shape' I want a section of game to be. A sine wave of rooms going both up and down? A 'stepped' progression? Just going straight up? I try and vary these shapes because that maximizes the effects of spatial memory in the player. Flow, pacing and aesthetics are also almost 'fractal'. So while the whole stage might have a shape, each seciton has a shape and each interaction has it's own pacing curve and blahblahblahblah, you don't actually explicitly DESIGN all this, but you FEEL it to make sure the level feels good and is varied. Since I tend to do rather long 'levels', I find it best to not plan too far ahead. I need to have a good feel for how one section of a level feels to make the next. Things rarely come out how I plan anyways.
Priorities for each game vary but you want to have uniqueness of movement and uniqueness of aesthetic. Aesthetics doesn't mean you have to have new assets in each section, but it means you should try and use the assets you have differently. I find that what I'm ultimately doing a lot is adjusting ratios. If I have a foresty level with some ruins/bricks, some part of the level will be all forest, some of it some brick and one more ruins heavy. Mix that up with things like the direction the player is traveling and a few set peieces, and you can have very memorable stages.
If you're doing longer stages, go look at Castlevania 1 and Castlevania 3 on the NES and look at how much they do with so little. You can head over to vgmaps.com to look at some of the techniques old level designers use.
If you're working smaller, go look at Super Meat Boy, which is surprisingly varied for many of the reasons I describe, despite rarely having unique per-stage assets. If you wanna go per screen, look at my game (I Wanna Be the Guy) or VVVVVVV.
Gameplay is obviously a top concern, but there is no good standard advice I can think of. Conversely, most amatuer games I play suffer from horridly bland level design, even on a movement and visual level. Everything is just samey and bland. Don't be one of those guys.