If you have minor stains on them, simply use a soft bristled toothbrush and warm soapy water to remove the stains.
For more serious stains, a cleaner such as this one can do wonders. Just make sure that you follow the instructions carefully.
If the whole shoe needs a clean, you can put the shoe(s) inside a pillowcase and put them inside the washing machine and run them on a cold setting. And let them air dry.