Here is a related thread.I've been using Shimano Mountain Bike Shoes SH-M086L for a few seasons now, I bought one pair and warrantied them since they fell apart. I wouldn't put that as a knock against them, they certainly were used well, but the failure wasn't typical hence the warranty. I won't be buying them again, but will probably graduate to a higher end mountain bike racing shoe.
And definitely use clipless. (Clipless being the ones with a cleat on your shoe and a locking mechanism on the pedal.)