From the shooting/composition/subject end, you really have to "think in black and white". Not so easy, really. The whole image will stand or fall on composition (lines, curves, diagonals, shapes, whatever it takes to make the eye work slowly and smoothly, with no jerking or hopping about, when viewing the finished article). That's something to think about before getting your camera out, and only by looking at thousands of successful b&w images can the 'method' begin to sink in. Think of rules of thirds, by all means, but in the end it's what the viewer's eyes do.
Secondly, forget relying on colour - it won't help at all in the long run and I've got hundreds of pictures that, even when taking the shot, thought might turn out well in b&w.... and simply didn't (though sometimes a desaturated, but not quite monochrome image may be a major improvement). I've never tried this myself, but I was once told that the "Raw+Jpeg" shooting option is quite good - and setting the camera to b&w - it will only affect the Jpeg and the Raw will still have the colour - but you'll see very quickly whether the shot is worth working on to make a good b&w - if it looks ok on the Jpeg, work on the Raw.
Think also of exposure and the dynamic range of the subject...... a little reading of Ansel Adams's Zone System can work well, if adapted to digital - you'll be wanting a full (or as full as possible) range of tones between black and white (in fact you don't really need the extremes of full black and full white, but a good range of tones in the middle is important). You may find yourself needing to use a ND Grad filter to help you balance the exposure and get more mid-tones.
So, ignore the colour, just look for shapes and lines - and gaze a little longer to see how your own eyes wander around the view. Once you've got the shot, have a look around for good tutorials about getting the best out of a b&w....... there are some good tips on this page at Photo Radar......
http://www.photoradar.com/search?keys=black+and+white&types=photoradar_tips%2Ctechnique_step_by_step