Most people say originality. I don't think this is the case, basically every area of music has been covered in some way, from droneworks to death metal, the music is there. So, instead of doing something 'new' I think it's important to create hybrids. A band that listens to a lot of different artists, from classical to electronic to anything, is going to fuse that into their music somehow. That's where the good stuff comes from, and the real originality.
I also HATE the band sensibility, if you will. I don't like it when bands say, "Oh, Jim is the guitar player, and there's only one Jim, so all he can play is guitar and he can only play one guitar line". I like layers, I like attention to detail. You can't get that with "bands", you can get it with a group of four guys making good music though.
That was a little all over the place, but basically it comes down to listening to a lot of music and being influenced by it, and not being afraid to make the music very dense.