I tend to always pick out the tileset first after picking a general theme and atmosphere, so I know what I can and can't utilize. I then pick possible music choices and then listen to them while designing the level on paper. When I get the general design decent, I build the level in JCS and refine the design there.
Considering I've yet to finish a level (aside from one-off mini-areas I only make to post at the screenshot thread), my method is probably not the best.